Rosetta Code

Compare sorting algorithms' performance: Difference between revisions

Page Discussion

Compare sorting algorithms' performance (view source)

Revision as of 16:26, 30 March 2017

11,160 bytes added ,  7 years ago
→‎{{header|Phix}}
m (→‎{{header|Go}}: improve conclusions)
Line 1,457:
 
The data fit curves of the character cell graph were combined with GCD +. function. This explains "1"s or other strange values where these curves intersect. Finally the scatter plots were multiplied by infinity and added to the best fit curves. The points didn't show up well using the same values as the curves.
 
=={{header|Phix}}==
<lang Phix>--
-- 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), c, mid, midn
object xi, midval
sequence left = {}, right = {}
 
if n<2 then
return x -- already sorted (trivial case)
end if
mid = floor((n+1)/2)
midval = x[mid]
x[mid] = x[1]
midn = 1
for i=2 to n do
xi = x[i]
c = compare(xi,midval)
if c<0 then
left &= xi
elsif c>0 then
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
integer first, last, stackptr, I, J, tmp, pivot
 
qstack = repeat(0,floor((length(s)/5)+10)) -- create a stack
 
first = 1
last = length(s)
stackptr = 0
while 1 do
while first<last do
pivot = s[floor(last+first)/2]
I = first
J = last
while 1 do
while s[I]<pivot do
I += 1
end while
while s[J]>pivot do
J -= 1
end while
if I>J then exit end if
if I<J then
tmp = s[I]
s[I] = s[J]
s[J] = tmp
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)
integer mins = min(s)
integer passes = max(max(s),abs(mins))
passes = floor(log10(passes))+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), j
object temp
while gap>0 do
for i=gap to length(s) do
temp = s[i]
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 gap, j, first, last
object xi, xj
 
last = length(x)
gap = floor(last/10)+1
while TRUE do
first = gap+1
for i=first to last do
xi = x[i]
j = i-gap
while TRUE do
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
sequence todo
--
-- 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 [$].
--
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
 
function esc_close(Ihandle /*ih*/, atom c)
if c=K_ESC then return IUP_CLOSE end if
return IUP_CONTINUE
end function
 
procedure main()
IupOpen(join_path({"..","pGUI"},1))
 
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)
IupSetAttributes(dlg, "RASTERSIZE=%dx%d", {640, 480})
IupSetAttribute(dlg, "TITLE", "Compare sorting algorithms")
IupSetCallback(dlg, "K_ANY", Icallback("esc_close"))
IupShow(dlg)
IupSetInt(tabs, "VALUEPOS", tabidx-1)
IupSetGlobalFunction("IDLE_ACTION", cb_idle_action)
IupMainLoop()
IupClose()
end procedure
 
main()</lang>
 
===Conclusions===
I knew bubblesort and insertion sort would be bad, but no so bad that you cannot meaningfully plot them against better sorts.
(logarithmic scale helps, but is still not enough)
I had no idea that (these particular implementations of) quicksort and shellsort would be so bad on a sequence of all 1s.
(so bad in fact that I had to cap that test length to 8,000 instead of 800,000 as used for the other tests)
The builtin sort and shell_sort2 were the clear winners, until I found a non-recursive quicksort that seems quite good.
IupPlot is brilliant! It is actually quite fun to watch the graphs grow as you get more results in!
There is a point where you realise you are currently wasting your life fretting over 0.015 seconds...
 
The ultimate conclusion is, of course, that there are some differences, but as long as you weed out the really bad
algorithms, and at least in the majority of cases, you will probably never notice whether sorting 800,000 items
takes 0.25s or 0.1s - more significant gains are likely to be found elsewhere.
 
=={{header|Python}}==
Petelomax
7,806

edits

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