Sort routines are varied and have different qualities - Probably the most desirable are ease/compactness of coding and speed.
Note. This article and the referenced MMBasic sort routines are really academic on the Micromite MkII.
CSubs for sorting the relevant data-type are included in the MMBasic download and attached top right and these should be used for single dimension arrays on the MX platform. Counterpart routines are not yet available for the MMX.
Discussions have raged for decades over which is the "best" and the reasons for the camps can be as varied as the sort methods. One thing is almost universally agreed: The Bubble sort is the slowest and generally to be avoided unless there is no alternative.
Here is a comparison of four routines that you will find in this library (in order of overall speed, slowest first):
*
Bubble Sort *
Shell Sort *
Cube Root of Two Sort *
Comb SortThe data used in this comparison is in the program DATA statements, the results are in the Attached CSV file along with an Excel spreadsheet with the graph. The graph is reproduced below but it is large to provide a trade off with scale Vs resolution.
Enjoy.
Note: The drop-off in Bubble sort timings is due to the sort being abandoned over 100 items.
The code:
Option base 0
cpu 48
Dim xx,yy,t As integer
xx=1000
Dim SP$(xx) length 20
print "Times in mS for the below sorts"
Print "No.","BBL","Shell","CR2","COMB"
print "------------------------------"
For yy = 5 To xx
print yy;",";
if yy<=100 then
InitSP yy:Timer=0
BblSort yy
t=Timer:Print t;",";
else
Print "0,";
end if
InitSP yy:Timer=0
ShellSort yy
t=Timer:Print t;",";
InitSP yy:Timer=0
CR2Sort yy
t=Timer:Print t;",";
InitSP yy:Timer=0
CombSort yy
t=Timer:Print t;",";
Print
Next
'-----------------------------------------------------------------
' comb sort
Sub CombSort(SPTop)
Local string M$
Local integer i, h, T=1, F=0, sw
Local float Gap=SPTop, Shrink=1.3
Do While Gap>1 Or Sw
Gap=Int(Gap/Shrink)
If Gap<1 Then Gap=1
i=1:Sw=F
For h=i+Gap To SPTop
If SP$(i)>SP$(h) Then
M$=SP$(i):SP$(i)=SP$(h):SP$(h)=M$:Sw=T
EndIf
i=i+1
Next
Loop
End Sub
'-----------------------------------------------------------------
' Cube Root of Two Sort
Sub CR2SORT(SPtop)
Local INTEGER i,x,b
Local FLOAT p,y
Local STRING a$
p=1.2599211: x=2: b=1: y=SPtop\2
While y>2: y=y/p: Wend
While x>1
y=y*p
x=SPtop\y
For i=0 To SPtop-x
If SP$(b+i)>SP$(x+i) Then a$=SP$(b+i):SP$(b+i)=SP$(x+i):SP$(x+i)=a$ 'SWAP SP$(b+i),SP$(x+i)
Next
Wend
End Sub
'-----------------------------------------------------------------
' Shell Sort
sub ShellSort(SPTop)
local integer i,j
local float k
local string a$
k = int(SPTop / 2)
WHILE k > 0
for i = 1 to SPTop
j = i
a$ = SP$(i)
WHILE (j >= k+1 and SP$(abs(j-k)) > a$)
SP$(j) = SP$(j-k)
j = j - k
wend
SP$(j) = a$
next
IF k = 2 THEN
k = 1
ELSE
k = int(k * 0.454545) ' 5/11
end if
WEND
end sub
'-----------------------------------------------------------------
' Bubble Sort
Sub BblSort(SPTop)
' SP$() is the array to be sorted
' SPTop is the number of elements in the array
Local integer Flips,n
Local string a$
Flips = 1
Do
Flips = 0
For n=0 To SPTop-1
' took out SWAP A$(n),A$(n+1) as it added 50% to the time
If SP$(n) > SP$(n+1) Then a$=SP$(n):SP$(n)=SP$(n+1):SP$(n+1)=a$:Flips = 1
Next
Loop While Flips = 1
End Sub
'-----------------------------------------------------------------
' Initialise the data-set
Sub InitSP (x)
Local integer n
Restore
For n=0 To x:Read SP$(n):Next
End Sub
Data "zak","sheila","fred","archie"
Data "jim","barry","alan","kevin"
Data "charles","steve","stephanie","jon"
Data "sonia","xavier","mark","adi"
Data "darren","paul","toby","jp"
Data "josie","kingsley","vod","oregon"
Data "lou anne","ian","syed","craig"
Data "james", "jules","judith","julie"
Data "fargo","david","hanson","dakota"
Data "picard", "riker", "morn", "quark"
Data "cisco", "morgan","bennett","white"
Data "black","brown","red","orange"
Data "green","blue","grey","violet"
Data "smith","kadiyam","shah","moore"
Data "saxton","murray","mitchell","alaie"
Data "aa","bb","cc","dd"
Data "ee","ff","gg","gg"
Data "zz","hh","ii","jj"
Data "hgjhg","ufyf","serg","iuyyrre"
Data "hiuhiuh","fdresppokm","khgugftrdtrhtfyguguF","gfhf"
Data "pic","micro","microchip","atmel"
Data "intel","zilog","amd","nvidia"
Data "mitsubishi","nissan","volkswagen","bmw"
Data "tesla","audi","toyota","honda"
Data "suzuki","yamaha","yamaha","kawasaki"
Data "mike"
Data "zak","sheila","fred","archie"
Data "jim","barry","alan","kevin"
Data "charles","steve","stephanie","jon"
Data "sonia","xavier","mark","adi"
Data "darren","paul","toby","jp"
Data "josie","kingsley","vod","oregon"
Data "lou anne","ian","syed","craig"
Data "james", "jules","judith","julie"
Data "fargo","david","hanson","dakota"
Data "picard", "riker", "morn", "quark"
Data "cisco", "morgan","bennett","white"
Data "black","brown","red","orange"
Data "green","blue","grey","violet"
Data "smith","kadiyam","shah","moore"
Data "saxton","murray","mitchell","alaie"
Data "aa","bb","cc","dd"
Data "ee","ff","gg","gg"
Data "zz","hh","ii","jj"
Data "hgjhg","ufyf","serg","iuyyrre"
Data "hiuhiuh","fdresppokm","khgugftrdtrhtfyguguF","gfhf"
Data "pic","micro","microchip","atmel"
Data "intel","zilog","amd","nvidia"
Data "mitsubishi","nissan","volkswagen","bmw"
Data "tesla","audi","toyota","honda"
Data "suzuki","yamaha","yamaha","kawasaki"
Data "mike"
Data "zak","sheila","fred","archie"
Data "jim","barry","alan","kevin"
Data "charles","steve","stephanie","jon"
Data "sonia","xavier","mark","adi"
Data "darren","paul","toby","jp"
Data "josie","kingsley","vod","oregon"
Data "lou anne","ian","syed","craig"
Data "james", "jules","judith","julie"
Data "fargo","david","hanson","dakota"
Data "picard", "riker", "morn", "quark"
Data "cisco", "morgan","bennett","white"
Data "black","brown","red","orange"
Data "green","blue","grey","violet"
Data "smith","kadiyam","shah","moore"
Data "saxton","murray","mitchell","alaie"
Data "aa","bb","cc","dd"
Data "ee","ff","gg","gg"
Data "zz","hh","ii","jj"
Data "hgjhg","ufyf","serg","iuyyrre"
Data "hiuhiuh","fdresppokm","khgugftrdtrhtfyguguF","gfhf"
Data "pic","micro","microchip","atmel"
Data "intel","zilog","amd","nvidia"
Data "mitsubishi","nissan","volkswagen","bmw"
Data "tesla","audi","toyota","honda"
Data "suzuki","yamaha","yamaha","kawasaki"
Data "mike"
Data "zak","sheila","fred","archie"
Data "jim","barry","alan","kevin"
Data "charles","steve","stephanie","jon"
Data "sonia","xavier","mark","adi"
Data "darren","paul","toby","jp"
Data "josie","kingsley","vod","oregon"
Data "lou anne","ian","syed","craig"
Data "james", "jules","judith","julie"
Data "fargo","david","hanson","dakota"
Data "picard", "riker", "morn", "quark"
Data "cisco", "morgan","bennett","white"
Data "black","brown","red","orange"
Data "green","blue","grey","violet"
Data "smith","kadiyam","shah","moore"
Data "saxton","murray","mitchell","alaie"
Data "aa","bb","cc","dd"
Data "ee","ff","gg","gg"
Data "zz","hh","ii","jj"
Data "hgjhg","ufyf","serg","iuyyrre"
Data "hiuhiuh","fdresppokm","khgugftrdtrhtfyguguF","gfhf"
Data "pic","micro","microchip","atmel"
Data "intel","zilog","amd","nvidia"
Data "mitsubishi","nissan","volkswagen","bmw"
Data "tesla","audi","toyota","honda"
Data "suzuki","yamaha","yamaha","kawasaki"
Data "mike"Data "zak","sheila","fred","archie"
Data "jim","barry","alan","kevin"
Data "charles","steve","stephanie","jon"
Data "sonia","xavier","mark","adi"
Data "darren","paul","toby","jp"
Data "josie","kingsley","vod","oregon"
Data "lou anne","ian","syed","craig"
Data "james", "jules","judith","julie"
Data "fargo","david","hanson","dakota"
Data "picard", "riker", "morn", "quark"
Data "cisco", "morgan","bennett","white"
Data "black","brown","red","orange"
Data "green","blue","grey","violet"
Data "smith","kadiyam","shah","moore"
Data "saxton","murray","mitchell","alaie"
Data "aa","bb","cc","dd"
Data "ee","ff","gg","gg"
Data "zz","hh","ii","jj"
Data "hgjhg","ufyf","serg","iuyyrre"
Data "hiuhiuh","fdresppokm","khgugftrdtrhtfyguguF","gfhf"
Data "pic","micro","microchip","atmel"
Data "intel","zilog","amd","nvidia"
Data "mitsubishi","nissan","volkswagen","bmw"
Data "tesla","audi","toyota","honda"
Data "suzuki","yamaha","yamaha","kawasaki"
Data "mike"
Data "zak","sheila","fred","archie"
Data "jim","barry","alan","kevin"
Data "charles","steve","stephanie","jon"
Data "sonia","xavier","mark","adi"
Data "darren","paul","toby","jp"
Data "josie","kingsley","vod","oregon"
Data "lou anne","ian","syed","craig"
Data "james", "jules","judith","julie"
Data "fargo","david","hanson","dakota"
Data "picard", "riker", "morn", "quark"
Data "cisco", "morgan","bennett","white"
Data "black","brown","red","orange"
Data "green","blue","grey","violet"
Data "smith","kadiyam","shah","moore"
Data "saxton","murray","mitchell","alaie"
Data "aa","bb","cc","dd"
Data "ee","ff","gg","gg"
Data "zz","hh","ii","jj"
Data "hgjhg","ufyf","serg","iuyyrre"
Data "hiuhiuh","fdresppokm","khgugftrdtrhtfyguguF","gfhf"
Data "pic","micro","microchip","atmel"
Data "intel","zilog","amd","nvidia"
Data "mitsubishi","nissan","volkswagen","bmw"
Data "tesla","audi","toyota","honda"
Data "suzuki","yamaha","yamaha","kawasaki"
Data "mike"
Data "zak","sheila","fred","archie"
Data "jim","barry","alan","kevin"
Data "charles","steve","stephanie","jon"
Data "sonia","xavier","mark","adi"
Data "darren","paul","toby","jp"
Data "josie","kingsley","vod","oregon"
Data "lou anne","ian","syed","craig"
Data "james", "jules","judith","julie"
Data "fargo","david","hanson","dakota"
Data "picard", "riker", "morn", "quark"
Data "cisco", "morgan","bennett","white"
Data "black","brown","red","orange"
Data "green","blue","grey","violet"
Data "smith","kadiyam","shah","moore"
Data "saxton","murray","mitchell","alaie"
Data "aa","bb","cc","dd"
Data "ee","ff","gg","gg"
Data "zz","hh","ii","jj"
Data "hgjhg","ufyf","serg","iuyyrre"
Data "hiuhiuh","fdresppokm","khgugftrdtrhtfyguguF","gfhf"
Data "pic","micro","microchip","atmel"
Data "intel","zilog","amd","nvidia"
Data "mitsubishi","nissan","volkswagen","bmw"
Data "tesla","audi","toyota","honda"
Data "suzuki","yamaha","yamaha","kawasaki"
Data "mike"Data "zak","sheila","fred","archie"
Data "jim","barry","alan","kevin"
Data "charles","steve","stephanie","jon"
Data "sonia","xavier","mark","adi"
Data "darren","paul","toby","jp"
Data "josie","kingsley","vod","oregon"
Data "lou anne","ian","syed","craig"
Data "james", "jules","judith","julie"
Data "fargo","david","hanson","dakota"
Data "picard", "riker", "morn", "quark"
Data "cisco", "morgan","bennett","white"
Data "black","brown","red","orange"
Data "green","blue","grey","violet"
Data "smith","kadiyam","shah","moore"
Data "saxton","murray","mitchell","alaie"
Data "aa","bb","cc","dd"
Data "ee","ff","gg","gg"
Data "zz","hh","ii","jj"
Data "hgjhg","ufyf","serg","iuyyrre"
Data "hiuhiuh","fdresppokm","khgugftrdtrhtfyguguF","gfhf"
Data "pic","micro","microchip","atmel"
Data "intel","zilog","amd","nvidia"
Data "mitsubishi","nissan","volkswagen","bmw"
Data "tesla","audi","toyota","honda"
Data "suzuki","yamaha","yamaha","kawasaki"
Data "mike"
Data "zak","sheila","fred","archie"
Data "jim","barry","alan","kevin"
Data "charles","steve","stephanie","jon"
Data "sonia","xavier","mark","adi"
Data "darren","paul","toby","jp"
Data "josie","kingsley","vod","oregon"
Data "lou anne","ian","syed","craig"
Data "james", "jules","judith","julie"
Data "fargo","david","hanson","dakota"
Data "picard", "riker", "morn", "quark"
Data "cisco", "morgan","bennett","white"
Data "black","brown","red","orange"
Data "green","blue","grey","violet"
Data "smith","kadiyam","shah","moore"
Data "saxton","murray","mitchell","alaie"
Data "aa","bb","cc","dd"
Data "ee","ff","gg","gg"
Data "zz","hh","ii","jj"
Data "hgjhg","ufyf","serg","iuyyrre"
Data "hiuhiuh","fdresppokm","khgugftrdtrhtfyguguF","gfhf"
Data "pic","micro","microchip","atmel"
Data "intel","zilog","amd","nvidia"
Data "mitsubishi","nissan","volkswagen","bmw"
Data "tesla","audi","toyota","honda"
Data "suzuki","yamaha","yamaha","kawasaki"
Data "mike"
Data "zak","sheila","fred","archie"
Data "jim","barry","alan","kevin"
Data "charles","steve","stephanie","jon"
Data "sonia","xavier","mark","adi"
Data "darren","paul","toby","jp"
Data "josie","kingsley","vod","oregon"
Data "lou anne","ian","syed","craig"
Data "james", "jules","judith","julie"
Data "fargo","david","hanson","dakota"
Data "picard", "riker", "morn", "quark"
Data "cisco", "morgan","bennett","white"
Data "black","brown","red","orange"
Data "green","blue","grey","violet"
Data "smith","kadiyam","shah","moore"
Data "saxton","murray","mitchell","alaie"
Data "aa","bb","cc","dd"
Data "ee","ff","gg","gg"
Data "zz","hh","ii","jj"
Data "hgjhg","ufyf","serg","iuyyrre"
Data "hiuhiuh","fdresppokm","khgugftrdtrhtfyguguF","gfhf"
Data "pic","micro","microchip","atmel"
Data "intel","zilog","amd","nvidia"
Data "mitsubishi","nissan","volkswagen","bmw"
Data "tesla","audi","toyota","honda"
Data "suzuki","yamaha","yamaha","kawasaki"
Data "mike"
Here is comparison between just the CR2 and Comb sorts with a larger array of 2200 items - with trend lines.
... and finally a comparison of Peter Mather's CSub StringSort (included as part of the MMBasic for MX170 download) versus the Comb with a thousand items. This illustrates the speed advantage of Machine code over interpreted MMBasic for comparable tasks. Even though the CSub is a bubble sort, the advantages of the machine code are obvious. Interestingly, note the characteristic "surges" in the sort times due to the algorithm and the "sweet-spot" of items versus time.
