Sort algorithms - A comparison

Modified on 2017/08/13 20:33 by CaptainBoing — Categorized as: Arrays, Memory, Sort, Strings

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 Sort

The 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.
Image


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.

Image

... 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.

Image