
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


Measure a relative performance of sorting algorithms implementations.

Plot execution time vs. input sequence length dependencies for various implementation of sorting algorithm and different input sequence types (example figures).

Consider three type of input sequences:

   ones: sequence of all 1's.   Example: {1, 1, 1, 1, 1}
   range: ascending sequence, i.e. already sorted.   Example: {1, 2, 3, 10, 15}
   shuffled range: sequence with elements randomly distributed.   Example: {5, 3, 9, 6, 8}


Consider at least two different sorting functions (different algorithms or/and different implementation of the same algorithm).

For example, consider Bubble Sort, Insertion sort, Quicksort or/and implementations of Quicksort with different pivot selection mechanisms.   Where possible, use existing implementations.

Preliminary subtask:

   Bubble Sort, Insertion sort, Quicksort, Radix sort, Shell sort
   Query Performance
   Write float arrays to a text file
   Plot x, y arrays
   Polynomial Fitting


General steps:

   Define sorting routines to be considered.
   Define appropriate sequence generators and write timings.
   Plot timings.
   What conclusions about relative performance of the sorting routines could be made based on the plots?


-- demo\rosetta\Compare_sorting_algorithms.exw
constant XQS = 01  -- (set to 1 to exclude quick_sort and shell_sort from ones)
 
include pGUI.e
 
Ihandle dlg, tabs, plot
Ihandles plots
 
function quick_sort2(sequence x)
    integer n = length(x)
    if n<2 then
        return x    -- already sorted (trivial case)
    end if
    integer mid = floor((n+1)/2),
            midn = 1
    object  midval = x[mid]
    sequence left = {}, right = {}
    x[mid] = x[1]
    for i=2 to n do
        object xi = x[i]
        integer c = compare(xi,midval)
        if c<0 then
            left = append(left,xi)
        elsif c>0 then
            right = append(right,xi)
        else
            midn += 1
        end if
    end for
 
    return quick_sort2(left) & repeat(midval,midn) & quick_sort2(right)
end function
 
function quick_sort(sequence s)
    sequence qstack = repeat(0,floor((length(s)/5)+10))   -- create a stack
    integer first = 1,
            last = length(s),
            stackptr = 0
    while true do
        while first<last do
            object pivot = s[floor(last+first)/2],
                   si, sj
            integer I = first,
                    J = last
            while true do
                while true do
                    si = s[I]
                    if si>=pivot then exit end if
                    I += 1
                end while
                while true do
                    sj = s[J]
                    if sj<=pivot then exit end if
                    J -= 1
                end while
                if I>J then exit end if
                if I<J then
                    if si=sj then
                        {I,J} = {J+1,I-1}
                        exit
                    end if
                    s[I] = sj
                    s[J] = si
                end if
                I += 1
                J -= 1
                if I>J then exit end if
            end while
            if I<last then
                qstack[stackptr+1] = I
                qstack[stackptr+2] = last
                stackptr += 2
            end if
            last = J
        end while
        if stackptr=0 then exit end if
        stackptr -= 2
        first = qstack[stackptr+1]
        last = qstack[stackptr+2]
    end while
    return s
end function
 
function radixSortn(sequence s, integer n)
    sequence buckets = repeat({},10)
    sequence res = {}
    for i=1 to length(s) do
        integer digit = remainder(floor(s[i]/power(10,n-1)),10)+1
        buckets[digit] = append(buckets[digit],s[i])
    end for
    for i=1 to length(buckets) do
        integer len = length(buckets[i])
        if len!=0 then
            if len=1 or n=1 then
                res &= buckets[i]
            else
                res &= radixSortn(buckets[i],n-1)
            end if
        end if
    end for
    return res
end function
 
function split_by_sign(sequence s)
    sequence buckets = {{},{}}
    for i=1 to length(s) do
        integer si = s[i]
        if si<0 then
            buckets[1] = append(buckets[1],-si)
        else
            buckets[2] = append(buckets[2],si)
        end if
    end for
    return buckets
end function
 
function radix_sort(sequence s)
-- NB this is an integer-only sort
    integer mins = min(s),
            passes = floor(log10(max(max(s),abs(mins))))+1
    if mins<0 then
        sequence buckets = split_by_sign(s)
        buckets[1] = reverse(sq_uminus(radixSortn(buckets[1],passes)))
        buckets[2] = radixSortn(buckets[2],passes)
        s = buckets[1]&buckets[2]
    else
        s = radixSortn(s,passes)
    end if
    return s
end function
 
function shell_sort(sequence s)
    integer gap = floor(length(s)/2)
    while gap>0 do
        for i=gap to length(s) do
            object temp = s[i]
            integer j = i-gap
            while j>=1 and temp<=s[j] do
                s[j+gap] = s[j]
                j -= gap
            end while
            s[j+gap] = temp
        end for
        gap = floor(gap/2)
    end while
    return s
end function
 
function shell_sort2(sequence x)
    integer last = length(x),
            gap = floor(last/10)+1
    while TRUE do
        integer first = gap+1
        for i=first to last do
            object xi = x[i]
            integer j = i-gap
            while TRUE do
                object xj = x[j]
                if xi>=xj then
                    j += gap
                    exit
                end if
                x[j+gap] = xj
                if j<=gap then
                    exit
                end if
                j -= gap
            end while
            x[j] = xi
        end for
        if gap=1 then
            return x
        else
            gap = floor(gap/3.5)+1
        end if
    end while
end function
 
function siftDown(sequence arr, integer s, integer last)
    integer root = s
    while root*2<=last do
        integer child = root*2
        if child<last and arr[child]<arr[child+1] then
            child += 1
        end if
        if arr[root]>=arr[child] then exit end if
        object tmp = arr[root]
        arr[root] = arr[child]
        arr[child] = tmp
        root = child
    end while
    return arr
end function
 
function heapify(sequence arr, integer count)
    integer s = floor(count/2)
    while s>0 do
        arr = siftDown(arr,s,count)
        s -= 1
    end while
    return arr
end function
 
function heap_sort(sequence arr)
    integer last = length(arr)
    arr = heapify(arr,last)
    while last>1 do
        object tmp = arr[1]
        arr[1] = arr[last]
        arr[last] = tmp
        last -= 1
        arr = siftDown(arr,1,last)
    end while
    return arr
end function
 
include builtins/sort.e
 
enum ONES = 1, SORTED = 2, RANDOM = 3, REVERSE = 4
 
constant tabtitles = {"ones","sorted","random","reverse"}
integer tabidx = 3
 
integer STEP
 
function tr(sequence name, integer rid=routine_id(name))
    return {name,rid}
end function
 
constant tests = {tr("quick_sort"),
                  tr("quick_sort2"),
                  tr("radix_sort"),
                  tr("shell_sort"),
                  tr("shell_sort2"),
                  tr("heap_sort"),
                  tr("sort"),           -- builtin
                 }
 
sequence results = repeat(repeat({}, length(tests)),length(tabtitles))
 
sequence dsdx = repeat(repeat(0,length(tests)),length(tabtitles))
 
integer ds_index
 
function idle_action_cb()
    atom best = -1, -- fastest last
         besti = 0, -- 1..length(tests) 
         bestt = 0, -- 1..length(tabtitles)
         len
    --
    -- Search for something to do, active/visible tab first.
    -- Any result set of length 0 -> just do one.
    -- Of all result sets<8, pick the lowest [$].
    --
    sequence todo = {tabidx}
    for t=1 to length(tabtitles) do
        if t!=tabidx then todo &= t end if
    end for
 
    for t=1 to length(tabtitles) do
        integer ti = todo[t]
        for i=1 to length(results[ti]) do
            len = length(results[ti][i])
            if len=0 then
                best = 0
                besti = i
                bestt = ti
                exit
            elsif len<8 then
                if (best=-1) or (best>results[ti][i][$]) then
                    best = results[ti][i][$]
                    besti = i
                    bestt = ti
                end if
            end if
        end for
        if (t=1) and (besti!=0) then exit end if
    end for
    if best>10 then
        -- cop out if it is getting too slow
        besti = 0
    end if
    if besti!=0 then
        STEP = iff(not XQS and bestt=ONES?1000:100000)
        len = (length(results[bestt][besti])+1)*STEP
        sequence test = iff(bestt=ONES?repeat(1,len):
                        iff(bestt=SORTED?tagset(len):
                        iff(bestt=RANDOM?shuffle(tagset(len)):
                        iff(bestt=REVERSE?reverse(tagset(len)):9/0))))
        ds_index = dsdx[bestt][besti]
        atom t0 = time()
        sequence check = call_func(tests[besti][2],{test})
        t0 = time()-t0
--      if check!=sort(test) then ?9/0 end if
        plot = plots[bestt]
        IupPlotInsert(plot, ds_index, -1, len, t0)
        results[bestt][besti] = append(results[bestt][besti],t0)
        IupSetAttribute(plot,"REDRAW",NULL)
        sequence progress = {bestt}
        for i=1 to length(results[bestt]) do
            progress &= length(results[bestt][i])
        end for
        IupSetStrAttribute(dlg,"TITLE","Compare sorting algorithms %s",{sprint(progress)})
        return IUP_CONTINUE
    end if
    IupSetAttribute(dlg,"TITLE","Compare sorting algorithms (all done, idle)")
    return IUP_IGNORE   -- all done, remove callback
end function
constant cb_idle_action = Icallback("idle_action_cb")
 
function tabchange_cb(Ihandle /*self*/, Ihandle /*new_tab*/)
    tabidx = IupGetInt(tabs,"VALUEPOS")+1
    plot = plots[tabidx]
    return IUP_DEFAULT;
end function
 
procedure main()
    IupOpen()
 
    plots = {}
    for i=1 to length(tabtitles) do
        if XQS then
--          results[ONES][1] = repeat(0,8)
            results[ONES][4] = repeat(0,8)
        end if
        plot = IupPlot()
        IupSetAttribute(plot,"MENUITEMPROPERTIES","YES")
        IupSetAttribute(plot,"TABTITLE",tabtitles[i])
        IupSetAttribute(plot,"GRID","YES")
        IupSetAttribute(plot,"MARGINLEFT","50")
        IupSetAttribute(plot,"MARGINBOTTOM","40")
        IupSetAttribute(plot,"LEGEND","YES")
        IupSetAttribute(plot,"LEGENDPOS","TOPLEFT")
--      IupSetAttribute(plot,"AXS_YSCALE","LOG10")
--      IupSetAttribute(plot,"AXS_XSCALE","LOG10")
        for j=1 to length(tests) do
            IupPlotBegin(plot)
            dsdx[i][j] = IupPlotEnd(plot)
            IupSetAttribute(plot,"DS_NAME",tests[j][1])
        end for
        plots = append(plots,plot)
    end for
    tabs = IupTabs(plots)
    IupSetCallback(tabs, "TABCHANGE_CB", Icallback("tabchange_cb"))
    dlg = IupDialog(tabs, "RASTERSIZE=800x480")
    IupSetAttribute(dlg, "TITLE", "Compare sorting algorithms")
    IupShow(dlg)
    IupSetInt(tabs, "VALUEPOS", tabidx-1)
    IupSetGlobalFunction("IDLE_ACTION", cb_idle_action)
    if platform()!=JS then
        IupMainLoop()
        IupClose()
    end if
end procedure
 
main()
