Quicksort

### Quicksort

function swap(a, i, j) 
    "swap two elements in an indexable sequence";
    local tmp := a[i];
    a[i] := a[j];
    a[j] := tmp;
end;


function random_list(size, maxr)
    "make list of length size of random number from 0 upto maxr";
    map( x -> random(maxr), range(0, size));
end;

function partition(a, lo, hi)
    "partition part of an indexable sequence a";
    local pivot := a[hi];
    local i := lo;
    local j := lo;
    while j < hi
        if a[j] < pivot 
            swap(a, i, j);
            i := i + 1;
        end;
        j := j + 1;
    end;
    swap(a, i, hi);
    i;
end;

function quick_sort (a, lo := 0, hi := length(a) - 1)    
    "quick sort an indexable sequence or part of it ";
    if lo < hi
        local p := partition(a, lo, hi);
        quick_sort(a, lo,    p - 1);
        quick_sort(a, p + 1, hi);
    end;
    a;
end;

# create list of lists/arrays/character sequences to be sorted
samples := [
    ## list of random integers
    random_list(32, 100), 
    ## Array of objects
    append(make_array(0), random_list(32,100)),                
    ## list of Characters
    append([], "pack my box with five dozen liquor jugs"), 
    ## list of versions
    [v"0.1.2",  v"0.1.2-pre1", v"0.1.2-pre2", v"0.1.3", v"0.1.2-pre1+10", v"1.2.3"] 
];

for data in  samples
    print(i"Using quick sort on:  $(type_of(data))\n");
    print(i"input=$(data)\n");
    quick_sort(data);
    print(i"output=$(data)\n\n");
end;

Output:

Using quick sort on:  class java.util.ArrayList
input=[68, 32, 60, 19, 63, 31, 58, 16, 26, 17, 4, 92, 96, 11, 57, 94, 65, 86, 98, 16, 77, 60, 83, 49, 63, 30, 28, 13, 22, 99, 1, 19]
output=[1, 4, 11, 13, 16, 16, 17, 19, 19, 22, 26, 28, 30, 31, 32, 49, 57, 58, 60, 60, 63, 63, 65, 68, 77, 83, 86, 92, 94, 96, 98, 99]

Using quick sort on:  class [Ljava.lang.Object;
input=[0, 78, 82, 61, 32, 96, 92, 31, 67, 8, 52, 85, 16, 97, 14, 62, 48, 78, 67, 40, 19, 60, 51, 21, 40, 22, 81, 25, 14, 82, 32, 95, 92]
output=[0, 8, 14, 14, 16, 19, 21, 22, 25, 31, 32, 32, 40, 40, 48, 51, 52, 60, 61, 62, 67, 67, 78, 78, 81, 82, 82, 85, 92, 92, 95, 96, 97]

Using quick sort on:  class java.util.ArrayList
input=[p, a, c, k,  , m, y,  , b, o, x,  , w, i, t, h,  , f, i, v, e,  , d, o, z, e, n,  , l, i, q, u, o, r,  , j, u, g, s]
output=[ ,  ,  ,  ,  ,  ,  , a, b, c, d, e, e, f, g, h, i, i, i, j, k, l, m, n, o, o, o, p, q, r, s, t, u, u, v, w, x, y, z]

Using quick sort on:  class java.util.ArrayList
input=[0.1.2, 0.1.2-pre1, 0.1.2-pre2, 0.1.3, 0.1.2-pre1+10, 1.2.3]
output=[0.1.2-pre1+10, 0.1.2-pre1, 0.1.2-pre2, 0.1.2, 0.1.3, 1.2.3]