Posts ID:273781 Favorites Creations Medals
 ID:273781   Apr 10 2011, 8:19 am So I was looking up sorting algorithms on wikipedia and found Cocktail Sort to be quite interesting. It's the same as bubble sort, only it makes passes in both directions, essentially cutting the sorting time in a little less than half. So if it took bubble sort 10 seconds, cocktail sort would take about 6 seconds. My question is, how would cocktail sort be programmed in DM? I'm not familiar with the language being used on the wikipedia page :\
It looks like Pascal.

First code is just basic sorting:
 ```proc/cocktailSort1(list/listToSort) var/swapped do swapped = 0 for(var/i = 1; i < listToSort.len; i++) if(listToSort[i] > listToSort[i + 1]) var/temp = listToSort[i] listToSort[i] = listToSort[i + 1] listToSort[i + 1] = temp swapped = 1 if(!swapped) break swapped = 0 for(var/i = listToSort.len - 1; i; i--) if(listToSort[i] > listToSort[i + 1]) var/temp = listToSort[i] listToSort[i] = listToSort[i + 1] listToSort[i + 1] = temp swapped = 1 while(swapped) ```

 ```proc/cocktailSort2(list/listToSort) var/swapped var/listBegin = 1 var/listEnd = listToSort.len do swapped = 0 for(var/i = listBegin + 1; i < listEnd; i++) if(listToSort[i] > listToSort[i + 1]) var/temp = listToSort[i] listToSort[i] = listToSort[i + 1] listToSort[i + 1] = temp swapped = 1 listEnd-- if(!swapped) break swapped = 0 for(var/i = listEnd - 1; i > listBegin - 1; i--) if(listToSort[i] > listToSort[i + 1]) var/temp = listToSort[i] listToSort[i] = listToSort[i + 1] listToSort[i + 1] = temp swapped = 1 listBegin++ while(swapped) ```

I nearly directly rewrote code, there's chance I got indexes wrong, or etc, but it seems to sort correctly.

Second one seems to be about 25% faster than first one.

Code I used for stress test:
 ```mob/verb/sort() stressTest(1000)proc/stressTest(num) var/list listToSort1 = list() listToSort2 = list() for(var/i = 0; i < num; i++) listToSort1 += roll(num * 10) listToSort2 += listToSort1 cocktailSort1(listToSort1) cocktailSort2(listToSort2) ```
In response to Zaoshi (#1)
Thanks for clarifying for me :)
 ```proc/cocktail_sort(list/L) var/swapped do swapped = 0 for(var/i=1,i L[i+1]) L.Swap(i,i+1) swapped = 1 if(!swapped) break swapped = 0 for(var/i=L.len-1,i>1,i--) if(L[i] < L[i-1]) L.Swap(i,i-1) swapped = 1 while(swapped) ```

 ```proc/cocktail_sort2(list/L) var/swapped var/start = 1 var/end = L.len do swapped = 0 for(var/i=start,i L[i+1]) L.Swap(i,i+1) swapped = 1 if(!swapped) break end -- swapped = 0 for(var/i=end,i>start,i--) if(L[i] < L[i-1]) L.Swap(i,i-1) swapped = 1 start ++ while(swapped) ```