Sorting an associative list

ID:1847278
 
May 7 2015, 2:09 pm
(See the best response by Lummox JR.)
This testthingy verb generates a random associated list.
Then the Bubble_sort() proc which I got off the forums here is supposed to sort it by its values.
But it doesn't work.
mob/verb/testthingy()
    var/list/l=new
    for(var/v in 1 to 20)
        l["[rand(1,9999)]"]=rand(1,9999)
    l=Bubble_sort(l)
    src<<"sorted values:"
    for(var/v in 1 to l.len)
        src<<l[l[v]]

proc/Bubble_sort(list/l)
    var i, j
    for(i=l.len,i>0,i--)
        for(j=1,j<i,j++)
            if(l[j]>l[j+1])
                l.Swap(j,j+1)
    return l


Here is what it prints out.

sorted values:
1257
594
561
8262
7711
2321
5629
4035
3933
4842
4601
997
2132
8482
7083
8238
6130
1289
3468
7981

Why doesn't it work? I've tried about 5 of the sorting procs I found on these forums and none of them work. Thanks

For example I tried these ones too:
proc/Sort_by_associative_value(list/l)
    if(l.len<=1) return l
    for(var/x=1,x<=l.len,x++)
        for(var/remain=l.len,remain>1,remain--)
            if(l[remain-1]<l[remain]) //change this line to if(l[remain-1]>l[remain]) for ascending order
                l.Swap(remain-1,remain)
    return l

proc/Sort_by_associative_value(list/l)
    var/min,i,j
    for(i=1 to l.len-1)
        min=l[l[i]]
        for(j=i+1 to l.len)
            if(l[l[j]]<min)
                min=j
        l.Swap(i,min)
    return l
May 7 2015, 2:38 pm
The reference says that Swap will retain the key/value pairs in an associative list, but I don't know what is going on here.
May 7 2015, 2:53 pm
Ah woops I noticed the error in the code, it works now that I changed it to this
proc/Bubble_sort(list/l)
    var i, j
    for(i=l.len,i>0,i--)
        for(j=1,j<i,j++)
            if(l[l[j]]>l[l[j+1]])
                l.Swap(j,j+1)
    return l
May 7 2015, 7:50 pm
Best response
Bubble sort is evil. Never use it.

For small lists, an insertion sort is much better. It does very little if the list is mostly sorted, and it does not suffer the problem of "turtles" a bubble sort has.

proc/InsertionSort(list/L)
    var/i,len=L.len,first,last,k,v
    for(i=2, i<=len, ++i)
        // look for an index from 1 to i-1 where L[i] belongs
        // this is a binary insertion sort, so it uses a binary search
        first = 1
        last = i-1
        v = L[i]   // make this L[L[i]] to sort by associated value
        while(first <= last)
            k = round((first+last) / 2)
            // if sorting by associated values, change L[k] to L[L[k]]
            if(v >= L[k]) first = k + 1
            else last = k - 1
        L.Insert(first, v)
        // cut after insertion, to keep the associated value intact
        L.Cut(i+1,i+2)

For large lists, the better bet is to use something like quicksort, and switch to insertion sort when that looks at smaller pieces. Insertion sort is still an O(N^2) operation, whereas quicksort, mergesort, heapsort, etc. are O(N log N).

Heapsort is fun because it can be done in place and it's relatively efficient. I actually use it in SotS II's pathfinding. The idea is that you turn the list into a max-heap (it's a binary tree, where each node is never smaller than either of its two branches). Then you keep popping the maximum value off the heap and repairing the heap till it's done.

Here's an implementation of heapsort:
proc/HeapSort(list/L)
    var/len=L.len, i
    /*
        Turn L into a max-heap. Start at the parent of the last node,
        and keep going all the way up to the root.

        The root, at index 1, will have the biggest value.
        Any node's children are at index*2 and index*2+1.
     */
    for(i=round(len/2), i>0, --i)
        _SiftDown(L, i, len)
    // Now keep popping the max element off and move it to the end
    while(len > 1)
        L.Swap(1, len--)
        _SiftDown(L, 1, len)  // repair the heap

proc/_SiftDown(list/L, root, end)
    // Move L[root] down as far as it will go
    var/child, s
    while(1)
        child = root*2   // left child index
        if(child > end) return
        // which is biggest: root, left child, or right child?
        s = (L[child] > L[root]) ? child : root
        if(child+1 <= end && L[child+1] > L[s]) s = child+1
        // if root is bigger than its children, the heap is good
        if(root == s) return
        // swap root with bigger child, then keep going
        L.Swap(root, s)
        root = s

There are more optimizations possible here that could eliminate proc call overhead for _SiftDown(), with the caveat that you'd want to look out for the built-in loop check if the list size got very large.
May 8 2015, 11:45 am
Oh cool, thanks.