Cocktail Sort?

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.len-1,i++)
      if(L[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<end,i++)
      if(L[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)