ID:273781 Apr 10 2011, 5: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 :\ Apr 10 2011, 6:09 am 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) Second adds little optimization by not sorting already sorted elements: 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) Apr 10 2011, 6:31 am (Edited on Apr 10 2011, 6:52 am) In response to Zaoshi 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) 