Bubble Sort

ID:169933
 
Apr 10 2005, 2:11 pm (Edited on Apr 10 2005, 2:32 pm)
I am trying to create a bubble sort proc, but I'm a bit stuck:

mob/verb/Test()
    var/list/nums = list(2,10,4,55)
    nums = BubbleSort(nums)
    world << list2text(nums)

proc/BubbleSort(var/list/L)
    var/remain = L.len + 1
    while(remain)
        remain --
        if(L[1] < L[2])
            L.Swap(1,2)
        if(L[2] < L[3])
            L.Swap(2,3)       
        if(L[3] < L[4])
            L.Swap(3,4)   
        sleep(0.1)
    return L


Using the Test() verb, I get the output(through list2text()) "55, 10, 4, 2". But if I were to make nums "2,44,1,66,46,77,22,99" I get the output "66, 44, 2, 1, 46, 77, 22, 99". This is because in BubbleSort(), I'm only swapping up to 4 things.

How can I swap n number of things?
Apr 10 2005, 2:34 pm
Here's what you're looking for, Death, but I recommend using the QuickSort algorithm instead anyway. =P

//Sorts L from greatest to least.
proc/bubble_sort(list/L)
    for(var/x = 1,x <= L.len,x++)
        for(var/remain = L.len,remain > 1,remain--)
            if(L[remain-1] < L[remain])
                L.Swap(remain - 1,remain)
Apr 10 2005, 4:40 pm
In response to Wizkidd0123
I've actually been working on a library of sorting routines. I've got a quicksort procedure that appears to work, but I can't get my shellsort to work.

I'll have to add a bubblesort.
Apr 10 2005, 7:31 pm
In response to Jp
hub://AbyssDragon.SortProcs =)
Apr 10 2005, 9:05 pm
In response to Crispy
Damn Abyssdragon, always getting to things before I do.

Next you'll be telling me he made a parsing system, or a library of basic mathematical procedures. :P
Apr 10 2005, 10:04 pm
In response to Jp
Damn Abyssdragon, always getting to things before I do.

Of course you can still build a practical sorting library. Abyssdragon's procs only sort text and numbers which isn't really practical as you generally also want to have their associated data also sorted. That and Abyssdragon uses a naive partition algorithm which produces really bad results if you are sorting an array which is in or close to reverse order.
Apr 11 2005, 4:39 am
In response to Crispy
I couldn't get that library to work.

I tried:

mob/verb/bubbles()
   var/list/nums = list(2,7,4,6)
   nums = BubbleSort(nums)
   world << list2text(nums)


My list2text proc came out blank.
Apr 11 2005, 4:44 am
In response to Theodis
None of them return anything, either. He should really fix that.
Apr 11 2005, 8:23 am
In response to DeathAwaitsU
DeathAwaitsU wrote:
I couldn't get that library to work.

I tried:
mob/verb/bubbles()
   var/list/nums = list(2,7,4,6)
   nums = BubbleSort(nums)
   world << list2text(nums)

My list2text proc came out blank.

It's been a while since I've looked at AbyssDragon.SortProcs, but I suspect BubbleSort() is sorting the list in place and does not return a value. Thus you're accidentally setting nums to null.

Lummox JR