How to order items(example: least to greatest)

ID:1399352
 
Oct 15 2013, 2:17 pm (Edited on Oct 16 2013, 6:45 am)
(See the best response by Ter13.)
 
var/list/items=newlist(/obj/sword{icon='sword.dmi';}, /obj/knife{icon='knife.dmi';}, /obj/gun{icon='gun.dmi';}, /obj/shield{icon='shield.dmi';}, /obj/spear{icon='spear.dmi';})

obj
    var/gold=0
    sword
        gold=10
    knife
        gold=2
    gun
        gold=15
    shield
        gold=12
    spear
        gold=7
mob/verb/order_items()
    var
        i
        j
        temphold
    for(i=1, i<items.len, i++)
        for(j=i+1, j<items.len+1, j++)
            var
                obj
                    a=items[i]
                    b=items[j]
            if(a.gold>b.gold)
                temphold=items[i]
                items[i]=items[j]
                items[j]=temphold
    var/
        obj
            a=items[1]
            b=items[2]
            c=items[3]
            d=items[4]
            e=items[5]
    src << "The items in order from least to greatest gold cost are [a], [b], [c], [d], [e]"
Oct 15 2013, 10:16 pm
 
for(j=i+1, j<items.len+1, j++)


What.
Oct 15 2013, 10:55 pm
Congratulations, you implemented Bubble Sort, the least efficient sorting algorithm out there.
Oct 15 2013, 11:57 pm (Edited on Oct 16 2013, 12:33 am)
Best response
I will hardly tackle sorting algorithms, but a better version of your sort would be quicksort. There are better sorting algorithms out there, though, and sorting is a very large topic I'd rather not go too deeply in.

What quicksort does, is break a list in half, then divide and conquer with a marching sort.

proc
    qs_partition(var/list/l,left,right,index)
        var/stor = 0
        pivot = l[index]
        stor = l[right]
        l[right] = l[index]
        l[index] = stor
        var/swap = left
        for(var/count=left;count<=right;count++)
            if(l[count]<=pivot)
                stor = l[count]
                l[count] = l[swap]
                l[swap] = stor
                swap++
        stor = l[swap]
        l[swap] = l[right]
        l[right] = stor
        return swap

    quicksort(var/list/l,left,right)
        if(left<right)
            var/pivot = (l[left]+l[right]+l[round((left+right)/2)])/3
            var/nindex = qs_partition(l,left,right,pivot)
            quicksort(l,left,nindex-1)
            quicksort(array,nindex+1,right)


There are some optimizations to this sort I haven't applied. Somtimes, it's best to eject out to an insertion sort once your pivot points get clustered enough, but that's a totally different post.
Oct 16 2013, 12:29 am (Edited on Nov 19 2013, 8:04 pm)
There's also always something like this: Making sure your lists are always in order.

I use a tree search to place new elements. You can set up your own value heuristic, and create a means of backing the list against useful data easily enough.

orderedlist
    var
        list/values = list()
    proc
        Add(var/value)
            if(value>=values[values.len])
                values += value
            else if(value<=values[1])
                values.Insert(1,value)
            else
                var/i = round(values.len/2)
                var/vpos = i
                while(i>1)
                    i = round(i/2)
                    if(values[vpos]>=value)
                        vpos += i
                    else
                        vpos -= i
                values.Insert(vpos+1,value)
        Remove(var/value)
            values -= value
        Get(var/index)
            return values[index]


Of course, it's really only meant to be used for things that don't have a lot of changes. Best to avoid sorting until the end if you are going to add a huge number of values to something, or if the value heuristic is unstable.