Quicksort

From Second Life Wiki
Jump to: navigation, search

Created by Kira Komarov.

This is an implementation of Quicksort by Tony Hoare. Since LSL deals mostly with lists, it is a nice platform to discuss divide-and-conquer sorting algorithms. The following are two different implementations: one for sorting integers and the other for sorting strings. The procedure is pretty much the same and the Quicksort function itself uses a comparer function which does the actual comparison between two elements of the same type. I have implemented it this way to show that one can work generically without having to necessarily adapt the Quicksort algorithm to every single case of the sorted type.

For integers:

// Gremlin: See Quicksort Integers, Quicksort Strings and Quicksort Map Stable
list sortIntegers = [ 3,7,8,5,2,1,9,5,4 ];
 
integer integerComparer(list a, list b) {
    if(llList2Integer(a, 0) <= llList2Integer(b, 0)) return TRUE;
    return FALSE;
}
 
list quicksort(list a) {
 
    if(llGetListLength(a) <= 1) return a;
 
    list pivot = llList2List(a, llGetListLength(a)/2, llGetListLength(a)/2);
    a = llDeleteSubList(a, llGetListLength(a)/2, llGetListLength(a)/2);
 
    list less = [];
    list more = [];
 
 
    integer i;
    for(i=0; i<llGetListLength(a); i++) {
        if(integerComparer(llList2List(a, i, i), pivot) == TRUE)
            less += llList2List(a, i, i);
        else
            more += llList2List(a, i, i);
    }
    return quicksort(less) + (list)pivot + quicksort(more);
 
}
 
default
{
    state_entry()
    {
        llOwnerSay("Sorted list contains in order: " + llDumpList2String(quicksort(sortIntegers), " "));
    } 
}

And for strings, the sort criteria is the lexicographical order of lowercase letters. You can easily change the alphabet by modifying the list alph, declared and initialised within the stringComparer() function. For example, you could use this to add your own sorting criteria. The relative order of elements is what makes the stringComparer() function work.

// Gremlin: See Quicksort Integers, Quicksort Strings and Quicksort Map Stable
list sortStrings = [ "aza", "aba", "aaa", "ana", "ban", "aaaa", "abarbecue" ];
 
integer stringComparer(list a, list b) {
 
    list alph = [ "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z" ];
 
    integer i;
 
    for(i=0; i<llStringLength(llList2String(a, 0)) && i<llStringLength(llList2String(b, 0)); i++) {
        if(llListFindList(alph, (list)llGetSubString(llList2String(a, 0), i, i)) < llListFindList(alph, (list)llGetSubString(llList2String(b, 0), i, i))) {
            return TRUE;
        }
        if(llListFindList(alph, (list)llGetSubString(llList2String(a, 0), i, i)) > llListFindList(alph, (list)llGetSubString(llList2String(b, 0), i, i))) {
            return FALSE;
        }
 
    }
    return TRUE;
}
 
list quicksort(list a) {
 
    if(llGetListLength(a) <= 1) return a;
 
    list pivot = llList2List(a, llGetListLength(a)/2, llGetListLength(a)/2);
    a = llDeleteSubList(a, llGetListLength(a)/2, llGetListLength(a)/2);
 
    list less = [];
    list more = [];
 
 
    integer i;
    for(i=0; i<llGetListLength(a); i++) {
        if(stringComparer(llList2List(a, i, i), pivot) == TRUE)
            less += llList2List(a, i, i);
        else
            more += llList2List(a, i, i);
    }
    return quicksort(less) + (list)pivot + quicksort(more);
 
}
 
default
{
    state_entry()
    {
        llOwnerSay("Sorted list contains in order: " + llDumpList2String(quicksort(sortStrings), " "));
    } 
}

As you can see between both versions, the quicksort() function makes use of lists being containers in order to work with data without type-casting to their corresponding types and thus changes only the comparer: integerComparer() and stringComparer() between the two versions given above. This allows you to create your own comparer function as plugins to Quicksort.