Rosetta Code

Compare sorting algorithms' performance: Difference between revisions

Page Discussion

Compare sorting algorithms' performance (view source)

Revision as of 14:32, 28 March 2021

71,357 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (→‎{{header|Phix}}: IupCloseOnEscape no longer needed)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 1,901:
=={{header|Phix}}==
{{libheader|Phix/pGUI}}
<!--<lang Phix>-- demo\rosetta\Compare_sorting_algorithms.exw>
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Compare_sorting_algorithms.exw</span>
constant XQS = 01 -- (set to 1 to exclude quick_sort and shell_sort from ones)
<span style="color: #008080;">constant</span> <span style="color: #000000;">XQS</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">01</span> <span style="color: #000080;font-style:italic;">-- (set to 1 to exclude quick_sort and shell_sort from ones)</span>
 
include pGUI.e
<span style="color: #008080;">include</span> <span style="color: #000000;">pGUI</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
 
Ihandle dlg, tabs, plot
<span style="color: #004080;">Ihandle</span> <span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tabs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">plot</span>
Ihandles plots
<span style="color: #004080;">Ihandles</span> <span style="color: #000000;">plots</span>
 
function quick_sort2(sequence x)
<span style="color: #008080;">function</span> <span style="color: #000000;">quick_sort2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
integer n = length(x), c, mid, midn
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
object xi, midval
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
sequence left = {}, right = {}
<span style="color: #008080;">return</span> <span style="color: #000000;">x</span> <span style="color: #000080;font-style:italic;">-- already sorted (trivial case)</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if n<2 then
<span style="color: #004080;">integer</span> <span style="color: #000000;">mid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">),</span>
return x -- already sorted (trivial case)
<span style="color: #000000;">midn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
end if
<span style="color: #004080;">object</span> <span style="color: #000000;">midval</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">left</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">right</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
mid = floor((n+1)/2)
<span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
midval = x[mid]
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
x[mid] = x[1]
<span style="color: #004080;">object</span> <span style="color: #000000;">xi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
midn = 1
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">midval</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
for i=2 to n do
<span style="color: #000000;">left</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">left</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xi</span><span style="color: #0000FF;">)</span>
xi = x[i]
<span style="color: #008080;">elsif</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
c = compare(xi,midval)
<span style="color: #000000;">right</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">right</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xi</span><span style="color: #0000FF;">)</span>
if c<0 then
<span left &style="color: xi#008080;">else</span>
<span style="color: #000000;">midn</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
elsif c>0 then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
right &= xi
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
else
midn += 1
<span style="color: #008080;">return</span> <span style="color: #000000;">quick_sort2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">left</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">&</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">midval</span><span style="color: #0000FF;">,</span><span style="color: #000000;">midn</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">quick_sort2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">right</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
end for
<span style="color: #008080;">function</span> <span style="color: #000000;">quick_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
return quick_sort2(left) & repeat(midval,midn) & quick_sort2(right)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">qstack</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">10</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- create a stack</span>
end function
<span style="color: #004080;">integer</span> <span style="color: #000000;">first</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
 
<span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span>
function quick_sort(sequence s)
<span style="color: #000000;">stackptr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
sequence qstack
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
integer first, last, stackptr, I, J, tmp, pivot
<span style="color: #008080;">while</span> <span style="color: #000000;">first</span><span style="color: #0000FF;"><</span><span style="color: #000000;">last</span> <span style="color: #008080;">do</span>
 
<span style="color: #004080;">object</span> <span style="color: #000000;">pivot</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">last</span><span style="color: #0000FF;">+</span><span style="color: #000000;">first</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span>
qstack = repeat(0,floor((length(s)/5)+10)) -- create a stack
<span style="color: #000000;">si</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sj</span>
 
<span style="color: #004080;">integer</span> <span style="color: #000000;">I</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">first</span><span style="color: #0000FF;">,</span>
first = 1
<span style="color: #000000;">J</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">last</span>
last = length(s)
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
stackptr = 0
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
while 1 do
<span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">I</span><span style="color: #0000FF;">]</span>
while first<last do
<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">pivot</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
pivot = s[floor(last+first)/2]
<span style="color: #000000;">I</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
I = first
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
J = last
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
while 1 do
<span style="color: #000000;">sj</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">J</span><span style="color: #0000FF;">]</span>
while s[I]<pivot do
<span style="color: #008080;">if</span> <span style="color: #000000;">sj</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">pivot</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
I += 1
<span style="color: #000000;">J</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
while s[J]>pivot do
<span style="color: #008080;">if</span> <span style="color: #000000;">I</span><span style="color: #0000FF;">></span><span style="color: #000000;">J</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
J -= 1
<span style="color: #008080;">if</span> <span style="color: #000000;">I</span><span style="color: #0000FF;"><</span><span style="color: #000000;">J</span> <span style="color: #008080;">then</span>
end while
<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">=</span><span style="color: #000000;">sj</span> <span style="color: #008080;">then</span>
if I>J then exit end if
<span style="color: #0000FF;">{</span><span style="color: #000000;">I</span><span style="color: #0000FF;">,</span><span style="color: #000000;">J</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">J</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">I</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
if I<J then
tmp <span style="color: s[I]#008080;">exit</span>
s[I] <span style="color: #008080;">end</span> <span style="color: s[J]#008080;">if</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">I</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sj</span>
s[J] = tmp
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">J</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
I += 1
<span style="color: #000000;">I</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
J -= 1
<span style="color: #000000;">J</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
if I>J then exit end if
<span style="color: #008080;">if</span> <span style="color: #000000;">I</span><span style="color: #0000FF;">></span><span style="color: #000000;">J</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
if I<last then
<span style="color: #008080;">if</span> <span style="color: #000000;">I</span><span style="color: #0000FF;"><</span><span style="color: #000000;">last</span> <span style="color: #008080;">then</span>
qstack[stackptr+1] = I
<span style="color: #000000;">qstack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">stackptr</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">I</span>
qstack[stackptr+2] = last
<span style="color: #000000;">qstack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">stackptr</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">last</span>
stackptr += 2
<span style="color: #000000;">stackptr</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">2</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
last = J
<span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">J</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
if stackptr=0 then exit end if
<span style="color: #008080;">if</span> <span style="color: #000000;">stackptr</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
stackptr -= 2
<span style="color: #000000;">stackptr</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">2</span>
first = qstack[stackptr+1]
<span style="color: #000000;">first</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">qstack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">stackptr</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
last = qstack[stackptr+2]
<span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">qstack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">stackptr</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return s
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
function radixSortn(sequence s, integer n)
<span style="color: #008080;">function</span> <span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
sequence buckets = repeat({},10)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">buckets</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
sequence res = {}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
for i=1 to length(s) do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer digit = remainder(floor(s[i]/power(10,n-1)),10)+1
<span style="color: #004080;">integer</span> <span style="color: #000000;">digit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]/</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
buckets[digit] = append(buckets[digit],s[i])
<span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
for i=1 to length(buckets) do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer len = length(buckets[i])
<span style="color: #004080;">integer</span> <span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
if len!=0 then
<span style="color: #008080;">if</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
if len=1 or n=1 then
<span style="color: #008080;">if</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">or</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
res &= buckets[i]
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
else
<span res &style="color: radixSortn(buckets[i],n-1)#008080;">else</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
return res
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
function split_by_sign(sequence s)
<span style="color: #008080;">function</span> <span style="color: #000000;">split_by_sign</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
sequence buckets = {{},{}}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">buckets</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{},{}}</span>
for i=1 to length(s) do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer si = s[i]
<span style="color: #004080;">integer</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
if si<0 then
<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
buckets[1] = append(buckets[1],-si)
<span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],-</span><span style="color: #000000;">si</span><span style="color: #0000FF;">)</span>
else
<span buckets[2] style="color: append(buckets[2],si)#008080;">else</span>
<span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">si</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
return buckets
<span style="color: #008080;">return</span> <span style="color: #000000;">buckets</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
function radix_sort(sequence s)
<span style="color: #008080;">function</span> <span style="color: #000000;">radix_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
integer mins = min(s)
<span style="color: #000080;font-style:italic;">-- NB this is an integer-only sort</span>
integer passes = max(max(s),abs(mins))
<span style="color: #004080;">integer</span> <span style="color: #000000;">mins</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span>
passes = floor(log10(passes))+1
<span style="color: #000000;">passes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">log10</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mins</span><span style="color: #0000FF;">))))+</span><span style="color: #000000;">1</span>
if mins<0 then
<span style="color: #008080;">if</span> <span style="color: #000000;">mins</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
sequence buckets = split_by_sign(s)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">buckets</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">split_by_sign</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
buckets[1] = reverse(sq_uminus(radixSortn(buckets[1],passes)))
<span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sq_uminus</span><span style="color: #0000FF;">(</span><span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">passes</span><span style="color: #0000FF;">)))</span>
buckets[2] = radixSortn(buckets[2],passes)
<span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">passes</span><span style="color: #0000FF;">)</span>
s = buckets[1]&buckets[2]
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]&</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
else
<span style="color: #008080;">else</span>
s = radixSortn(s,passes)
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">passes</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return s
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
function shell_sort(sequence s)
<span style="color: #008080;">function</span> <span style="color: #000000;">shell_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
integer gap = floor(length(s)/2), j
<span style="color: #004080;">integer</span> <span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
object temp
<span style="color: #008080;">while</span> <span style="color: #000000;">gap</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
while gap>0 do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">gap</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
for i=gap to length(s) do
<span style="color: #004080;">object</span> <span style="color: #000000;">temp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
temp = s[i]
<span style="color: #004080;">integer</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">gap</span>
j = i-gap
<span style="color: #008080;">while</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">temp</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
while j>=1 and temp<=s[j] do
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
s[j+gap] = s[j]
<span style="color: #000000;">j</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">gap</span>
j -= gap
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">temp</span>
s[j+gap] = temp
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
gap = floor(gap/2)
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
end while
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
return s
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
end function
 
<span style="color: #008080;">function</span> <span style="color: #000000;">shell_sort2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
function shell_sort2(sequence x)
<span style="color: #004080;">integer</span> <span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">),</span>
integer gap, j, first, last
<span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">last</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
object xi, xj
<span style="color: #008080;">while</span> <span style="color: #004600;">TRUE</span> <span style="color: #008080;">do</span>
 
<span style="color: #004080;">integer</span> <span style="color: #000000;">first</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">gap</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
last = length(x)
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">first</span> <span style="color: #008080;">to</span> <span style="color: #000000;">last</span> <span style="color: #008080;">do</span>
gap = floor(last/10)+1
<span style="color: #004080;">object</span> <span style="color: #000000;">xi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
while TRUE do
<span style="color: #004080;">integer</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">gap</span>
first = gap+1
<span style="color: #008080;">while</span> <span style="color: #004600;">TRUE</span> <span style="color: #008080;">do</span>
for i=first to last do
<span style="color: #004080;">object</span> <span style="color: #000000;">xj</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
xi = x[i]
<span style="color: #008080;">if</span> <span style="color: #000000;">xi</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">xj</span> <span style="color: #008080;">then</span>
j = i-gap
<span style="color: #000000;">j</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">gap</span>
while TRUE do
xj <span style="color: x[j]#008080;">exit</span>
if xi<span style="color: #008080;">end</span> <span style=xj"color: then#008080;">if</span>
<span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xj</span>
j += gap
<span style="color: #008080;">if</span> <span style="color: #000000;">j</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">gap</span> <span style="color: #008080;">then</span>
exit
end if <span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
x[j+gap] = xj
<span style="color: #000000;">j</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">gap</span>
if j<=gap then
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
exit
<span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xi</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
j -= gap
<span style="color: #008080;">if</span> <span style="color: #000000;">gap</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
end while
<span style="color: #008080;">return</span> <span style="color: #000000;">x</span>
x[j] = xi
<span style="color: #008080;">else</span>
end for
<span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">/</span><span style="color: #000000;">3.5</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
if gap=1 then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return x
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
else
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
gap = floor(gap/3.5)+1
end if
<span style="color: #008080;">function</span> <span style="color: #000000;">siftDown</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">)</span>
end while
<span style="color: #004080;">integer</span> <span style="color: #000000;">root</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
end function
<span style="color: #008080;">while</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">last</span> <span style="color: #008080;">do</span>
 
<span style="color: #004080;">integer</span> <span style="color: #000000;">child</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span>
function siftDown(sequence arr, integer s, integer last)
<span style="color: #008080;">if</span> <span style="color: #000000;">child</span><span style="color: #0000FF;"><</span><span style="color: #000000;">last</span> <span style="color: #008080;">and</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
integer root = s
<span style="color: #000000;">child</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
while root*2<=last do
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
integer child = root*2
<span style="color: #008080;">if</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">]>=</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if child<last and arr[child]<arr[child+1] then
<span style="color: #004080;">object</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">]</span>
child += 1
<span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">]</span>
end if
<span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tmp</span>
if arr[root]>=arr[child] then exit end if
<span style="color: #000000;">root</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">child</span>
object tmp = arr[root]
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
arr[root] = arr[child]
<span style="color: #008080;">return</span> <span style="color: #000000;">arr</span>
arr[child] = tmp
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
root = child
end while
<span style="color: #008080;">function</span> <span style="color: #000000;">heapify</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">)</span>
return arr
<span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">count</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
end function
<span style="color: #008080;">while</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
 
<span style="color: #000000;">arr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">siftDown</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">)</span>
function heapify(sequence arr, integer count)
<span style="color: #000000;">s</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
integer s = floor(count/2)
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
while s>0 do
<span style="color: #008080;">return</span> <span style="color: #000000;">arr</span>
arr = siftDown(arr,s,count)
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
s -= 1
end while
<span style="color: #008080;">function</span> <span style="color: #000000;">heap_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">)</span>
return arr
<span style="color: #004080;">integer</span> <span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">)</span>
end function
<span style="color: #000000;">arr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">heapify</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">last</span><span style="color: #0000FF;">)</span>
 
<span style="color: #008080;">while</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
function heap_sort(sequence arr)
<span style="color: #004080;">object</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
integer last = length(arr)
<span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">last</span><span style="color: #0000FF;">]</span>
arr = heapify(arr,last)
<span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">last</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tmp</span>
while last>1 do
<span style="color: #000000;">last</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
object tmp = arr[1]
<span style="color: #000000;">arr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">siftDown</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">last</span><span style="color: #0000FF;">)</span>
arr[1] = arr[last]
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
arr[last] = tmp
<span style="color: #008080;">return</span> <span style="color: #000000;">arr</span>
last -= 1
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
arr = siftDown(arr,1,last)
end while
<span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">/</span><span style="color: #7060A8;">sort</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
return arr
end function
<span style="color: #008080;">enum</span> <span style="color: #000000;">ONES</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">SORTED</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">RANDOM</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">REVERSE</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span>
 
include builtins/sort.e
<span style="color: #008080;">constant</span> <span style="color: #000000;">tabtitles</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"ones"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"sorted"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"random"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"reverse"</span><span style="color: #0000FF;">}</span>
 
<span style="color: #004080;">integer</span> <span style="color: #000000;">tabidx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span>
enum ONES = 1, SORTED = 2, RANDOM = 3, REVERSE = 4
 
<span style="color: #004080;">integer</span> <span style="color: #000000;">STEP</span>
constant tabtitles = {"ones","sorted","random","reverse"}
integer tabidx = 3
<span style="color: #008080;">function</span> <span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">name</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">rid</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">routine_id</span><span style="color: #0000FF;">(</span><span style="color: #000000;">name</span><span style="color: #0000FF;">))</span>
 
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">name</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rid</span><span style="color: #0000FF;">}</span>
integer STEP
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
function tr(sequence name, integer rid=routine_id(name))
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"quick_sort"</span><span style="color: #0000FF;">),</span>
return {name,rid}
<span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"quick_sort2"</span><span style="color: #0000FF;">),</span>
end function
<span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"radix_sort"</span><span style="color: #0000FF;">),</span>
 
<span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"shell_sort"</span><span style="color: #0000FF;">),</span>
constant tests = {tr("quick_sort"),
<span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"shell_sort2"</span><span style="color: #0000FF;">),</span>
tr("quick_sort2"),
<span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"heap_sort"</span><span style="color: #0000FF;">),</span>
tr("radix_sort"),
<span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"sort"</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- builtin</span>
tr("shell_sort"),
tr(<span style="shell_sort2color: #0000FF;"),>}</span>
tr("heap_sort"),
<span style="color: #004080;">sequence</span> <span style="color: #000000;">results</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({},</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabtitles</span><span style="color: #0000FF;">))</span>
tr("sort"), -- builtin
}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dsdx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabtitles</span><span style="color: #0000FF;">))</span>
 
sequence results = repeat(repeat({}, length(tests)),length(tabtitles))
<span style="color: #004080;">integer</span> <span style="color: #000000;">ds_index</span>
 
sequence dsdx = repeat(repeat(0,length(tests)),length(tabtitles))
<span style="color: #008080;">function</span> <span style="color: #000000;">idle_action_cb</span><span style="color: #0000FF;">()</span>
 
<span style="color: #004080;">atom</span> <span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- fastest last</span>
integer ds_index
<span style="color: #000000;">besti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- 1..length(tests) </span>
 
<span style="color: #000000;">bestt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- 1..length(tabtitles)</span>
function idle_action_cb()
<span style="color: #000000;">len</span>
atom best = -1, -- fastest last
<span style="color: #000080;font-style:italic;">--
besti = 0, -- 1..length(tests)
-- Search for something to do, active/visible tab first.
bestt = 0, -- 1..length(tabtitles)
-- Any result set of length 0 -&gt; just do one.
len
-- Of all result sets&lt;8, pick the lowest [$].
sequence todo
--</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">todo</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">tabidx</span><span style="color: #0000FF;">}</span>
-- Search for something to do, active/visible tab first.
<span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabtitles</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
-- Any result set of length 0 -> just do one.
<span style="color: #008080;">if</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">tabidx</span> <span style="color: #008080;">then</span> <span style="color: #000000;">todo</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">t</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- Of all result sets<8, pick the lowest [$].
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
--
todo = {tabidx}
<span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabtitles</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
for t=1 to length(tabtitles) do
<span style="color: #004080;">integer</span> <span style="color: #000000;">ti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">todo</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]</span>
if t!=tabidx then todo &= t end if
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
end for
<span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
 
<span style="color: #008080;">if</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
for t=1 to length(tabtitles) do
<span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
integer ti = todo[t]
<span style="color: #000000;">besti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
for i=1 to length(results[ti]) do
<span style="color: #000000;">bestt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ti</span>
len = length(results[ti][i])
if len <span style=0"color: then#008080;">exit</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">len</span><span style="color: #0000FF;"><</span><span style="color: #000000;">8</span> <span style="color: #008080;">then</span>
best = 0
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">best</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">best</span><span style="color: #0000FF;">></span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][$])</span> <span style="color: #008080;">then</span>
besti = i
<span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][$]</span>
bestt = ti
<span style="color: #000000;">besti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
exit
<span style="color: #000000;">bestt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ti</span>
elsif len<8 then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if (best=-1) or (best>results[ti][i][$]) then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
best = results[ti][i][$]
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
besti = i
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">besti</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
bestt = ti
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end if
<span style="color: #008080;">if</span> <span style="color: #000000;">best</span><span style="color: #0000FF;">></span><span style="color: #000000;">10</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000080;font-style:italic;">-- cop out if it is getting too slow</span>
end for
<span style="color: #000000;">besti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
if (t=1) and (besti!=0) then exit end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">if</span> <span style="color: #000000;">besti</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
if best>10 then
<span style="color: #000000;">STEP</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #008080;">not</span> <span style="color: #000000;">XQS</span> <span style="color: #008080;">and</span> <span style="color: #000000;">bestt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ONES</span><span style="color: #0000FF;">?</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">:</span><span style="color: #000000;">100000</span><span style="color: #0000FF;">)</span>
-- cop out if it is getting too slow
<span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">][</span><span style="color: #000000;">besti</span><span style="color: #0000FF;">])+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">STEP</span>
besti = 0
<span style="color: #004080;">sequence</span> <span style="color: #000000;">test</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ONES</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">):</span>
end if
<span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">SORTED</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">len</span><span style="color: #0000FF;">):</span>
if besti!=0 then
<span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">RANDOM</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">len</span><span style="color: #0000FF;">)):</span>
STEP = iff(not XQS and bestt=ONES?1000:100000)
<span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">REVERSE</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">len</span><span style="color: #0000FF;">)):</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span><span style="color: #0000FF;">))))</span>
len = (length(results[bestt][besti])+1)*STEP
<span style="color: #000000;">ds_index</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dsdx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">][</span><span style="color: #000000;">besti</span><span style="color: #0000FF;">]</span>
sequence test = iff(bestt=ONES?repeat(1,len):
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
iff(bestt=SORTED?tagset(len):
<span style="color: #004080;">sequence</span> <span style="color: #000000;">check</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">call_func</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">besti</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],{</span><span style="color: #000000;">test</span><span style="color: #0000FF;">})</span>
iff(bestt=RANDOM?shuffle(tagset(len)):
<span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span>
iff(bestt=REVERSE?reverse(tagset(len)):9/0))))
<span style="color: #000080;font-style:italic;">-- if check!=sort(test) then ?9/0 end if</span>
ds_index = dsdx[bestt][besti]
<span style="color: #000000;">plot</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">plots</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">]</span>
atom t0 = time()
<span style="color: #7060A8;">IupPlotInsert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ds_index</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
sequence check = call_func(tests[besti][2],{test})
<span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">][</span><span style="color: #000000;">besti</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">][</span><span style="color: #000000;">besti</span><span style="color: #0000FF;">],</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
t0 = time()-t0
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"REDRAW"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">)</span>
-- if check!=sort(test) then ?9/0 end if
<span style="color: #004080;">sequence</span> <span style="color: #7060A8;">progress</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">}</span>
plot = plots[bestt]
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
IupPlotInsert(plot, ds_index, -1, len, t0)
<span style="color: #7060A8;">progress</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
results[bestt][besti] = append(results[bestt][besti],t0)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
IupSetAttribute(plot,"REDRAW",NULL)
<span style="color: #7060A8;">IupSetStrAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"TITLE"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Compare sorting algorithms %s"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">progress</span><span style="color: #0000FF;">)})</span>
sequence progress = {bestt}
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_CONTINUE</span>
for i=1 to length(results[bestt]) do
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
progress &= length(results[bestt][i])
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"TITLE"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Compare sorting algorithms (all done, idle)"</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_IGNORE</span> <span style="color: #000080;font-style:italic;">-- all done, remove callback</span>
IupSetStrAttribute(dlg,"TITLE","Compare sorting algorithms %s",{sprint(progress)})
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
return IUP_CONTINUE
<span style="color: #008080;">constant</span> <span style="color: #000000;">cb_idle_action</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">Icallback</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"idle_action_cb"</span><span style="color: #0000FF;">)</span>
end if
IupSetAttribute(dlg,"TITLE","Compare sorting algorithms (all done, idle)")
<span style="color: #008080;">function</span> <span style="color: #000000;">tabchange_cb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">Ihandle</span> <span style="color: #000080;font-style:italic;">/*self*/</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">Ihandle</span> <span style="color: #000080;font-style:italic;">/*new_tab*/</span><span style="color: #0000FF;">)</span>
return IUP_IGNORE -- all done, remove callback
<span style="color: #000000;">tabidx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupGetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabs</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"VALUEPOS"</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
end function
<span style="color: #000000;">plot</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">plots</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tabidx</span><span style="color: #0000FF;">]</span>
constant cb_idle_action = Icallback("idle_action_cb")
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_DEFAULT</span><span style="color: #0000FF;">;</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function tabchange_cb(Ihandle /*self*/, Ihandle /*new_tab*/)
tabidx = IupGetInt(tabs,"VALUEPOS")+1
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
plot = plots[tabidx]
<span style="color: #7060A8;">IupOpen</span><span style="color: #0000FF;">()</span>
return IUP_DEFAULT;
end function
<span style="color: #000000;">plots</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
 
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabtitles</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
procedure main()
<span style="color: #008080;">if</span> <span style="color: #000000;">XQS</span> <span style="color: #008080;">then</span>
IupOpen()
<span style="color: #000080;font-style:italic;">-- results[ONES][1] = repeat(0,8)</span>
 
<span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ONES</span><span style="color: #0000FF;">][</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">)</span>
plots = {}
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
for i=1 to length(tabtitles) do
<span style="color: #000000;">plot</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupPlot</span><span style="color: #0000FF;">()</span>
if XQS then
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"MENUITEMPROPERTIES"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"YES"</span><span style="color: #0000FF;">)</span>
-- results[ONES][1] = repeat(0,8)
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"TABTITLE"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tabtitles</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
results[ONES][4] = repeat(0,8)
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"GRID"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"YES"</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"MARGINLEFT"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"50"</span><span style="color: #0000FF;">)</span>
plot = IupPlot()
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"MARGINBOTTOM"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"40"</span><span style="color: #0000FF;">)</span>
IupSetAttribute(plot,"MENUITEMPROPERTIES","YES")
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"LEGEND"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"YES"</span><span style="color: #0000FF;">)</span>
IupSetAttribute(plot,"TABTITLE",tabtitles[i])
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"LEGENDPOS"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"TOPLEFT"</span><span style="color: #0000FF;">)</span>
IupSetAttribute(plot,"GRID","YES")
<span style="color: #000080;font-style:italic;">-- IupSetAttribute(plot,"MARGINLEFTAXS_YSCALE","50LOG10")
-- IupSetAttribute(plot,"MARGINBOTTOMAXS_XSCALE","40LOG10")</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
IupSetAttribute(plot,"LEGEND","YES")
<span style="color: #7060A8;">IupPlotBegin</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">)</span>
IupSetAttribute(plot,"LEGENDPOS","TOPLEFT")
<span style="color: #000000;">dsdx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupPlotEnd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">)</span>
-- IupSetAttribute(plot,"AXS_YSCALE","LOG10")
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"DS_NAME"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
-- IupSetAttribute(plot,"AXS_XSCALE","LOG10")
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
for j=1 to length(tests) do
<span style="color: #000000;">plots</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plots</span><span style="color: #0000FF;">,</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">)</span>
IupPlotBegin(plot)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
dsdx[i][j] = IupPlotEnd(plot)
<span style="color: #000000;">tabs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupTabs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plots</span><span style="color: #0000FF;">)</span>
IupSetAttribute(plot,"DS_NAME",tests[j][1])
<span style="color: #7060A8;">IupSetCallback</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabs</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"TABCHANGE_CB"</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">Icallback</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"tabchange_cb"</span><span style="color: #0000FF;">))</span>
end for
<span style="color: #000000;">dlg</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupDialog</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabs</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"RASTERSIZE=800x480"</span><span style="color: #0000FF;">)</span>
plots = append(plots,plot)
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"TITLE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"Compare sorting algorithms"</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #7060A8;">IupShow</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">)</span>
tabs = IupTabs(plots)
<span style="color: #7060A8;">IupSetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabs</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"VALUEPOS"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tabidx</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
IupSetCallback(tabs, "TABCHANGE_CB", Icallback("tabchange_cb"))
<span style="color: #7060A8;">IupSetGlobalFunction</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"IDLE_ACTION"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cb_idle_action</span><span style="color: #0000FF;">)</span>
dlg = IupDialog(tabs)
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
IupSetAttributes(dlg, "RASTERSIZE=%dx%d", {640, 480})
<span style="color: #7060A8;">IupMainLoop</span><span style="color: #0000FF;">()</span>
IupSetAttribute(dlg, "TITLE", "Compare sorting algorithms")
<span style="color: #7060A8;">IupClose</span><span style="color: #0000FF;">()</span>
IupShow(dlg)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
IupSetInt(tabs, "VALUEPOS", tabidx-1)
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
IupSetGlobalFunction("IDLE_ACTION", cb_idle_action)
IupMainLoop()
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
IupClose()
<!--</lang>-->
end procedure
 
main()</lang>
 
===Conclusions===
I knew bubblesort and insertion sort would be bad, but not so bad that you cannot meaningfully plot them against better sorts.
Petelomax
7,813

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/53725"