(simple) sorts comparison

[tsh73]

There is insertion sort popped up in our curriculum so I went and compared some sorts I thought I knew.
Namely insertion sort, select sort and bubble sort.

Interesting thing - I checked Wikipedia after and see that all my implementations differ from Wikipedia ones!
Like, select sort works by finding max instead of min
insertion sorts touches 0-th item of array so it wouldn't work with array starting from 0
(and adding IF/EXIT WHILE for "out of array" check significantly slows it down!)
Though I pretty sure insertion sort / select sort work as fast as they could (?)
but bubble sorts in Wikipedia quite differ from my version.
May be they perform significantly better?

'bubbleSort vs select vs insertion sort
N=300
'N=10
s=0.5
randomize s 'if you want them to be the same
dim a(N)
dim b(N)
print "N=";N
print "tInsertion", "tSelect","tBubble", "ins/bubble","sel/bubble"

for nExp=1 to 20
scan

'generate
for i = 1 to N
   b(i)=int(rnd(0)*900)+100'-500
next
'prepare
for i = 1 to N
   a(i)=b(i)
next

'print "src"
'gosub [printArr]

[bubbleSort]
'prepare
for i = 1 to N
   a(i)=b(i)
next

t0=time$("ms")
for j=N-1 to 1 step -1  'number of pairs
   for i = 1 to j
       if a(i)> a(i+1) then tmp=a(i):a(i)=a(i+1):a(i+1)=tmp
   next
'gosub [printArr]
next
tBubble=time$("ms")-t0

[selectSort]
'prepare
for i = 1 to N
   a(i)=b(i)
next

t0=time$("ms")
for j=N to 2 step -1    'unsorted length
   maxPos=1:maxItem=a(1)   'find the max in unsorted
   for i = 2 to j
       if a(i)> maxItem then maxItem=a(i):maxPos=i
   next
   a(maxPos)=a(j):a(j)=maxItem 'swap it with last unsorted
'gosub [printArr]
next
tSelect=time$("ms")-t0

[insertion]
'prepare
for i = 1 to N
   a(i)=b(i)
next

t0=time$("ms")
for j=2 to N '1 is sorted, start with 2
   i=j
'    while a(i)<a(i-1)  'works only if a(0) less them min(a())
   tmp=a(i)
   while (tmp<a(i-1)) AND (i>1) 'touches a(0) (so from 0 will not work) but not uses it
       a(i)=a(i-1)
       i=i-1
   wend
   a(i)=tmp
'gosub [printArr]
next
tInsertion=time$("ms")-t0

'print "res"
'gosub [printArr]

print tInsertion, tSelect, tBubble, int((tInsertion/tBubble)*100);"%",int((tSelect/tBubble)*100);"%"
s1=s1+tInsertion
s2=s2+tSelect
s3=s3+tBubble

next    'experiment
print "-- avg --------------------"
print int(s1/20), int(s2/20), int(s3/20), int((s1/ s3)*100);"%", int((s2/ s3)*100);"%"

end
[printArr]
   for p.i=1 to N
       print a(p.i);" ";
   next
   print
return


[Rod]

There is a classic Quick Sort routine ships with Just BASIC v2 Also Bplus posted one recently and I modified it to sort a multi column table using more than one column if required.


'This code uses a modified quicksort routine
'to sort on multiple columns of a data set

dim dbf$(25,10)
print "Unsorted Set"
for row=1 to 25
   for col=1 to 10
       dbf$(row,col)=str$(int(rnd(0)*9+.5))
       print dbf$(row,col);" ";
   next
   print
next

'provide the starting row, ending row and the number of columns
'and comma delimited string of the column numbers to sort on
'in priority order. This example sorts column3 in order within
'column2
call qsort 1,25,10,"2,3"

print "Sorted Set"
for row=1 to 25
   for col=1 to 10
       print dbf$(row,col);" ";
   next
   print
next
wait

sub qsort Start, Finish, numCol, order$
 'order$ is a comma delimited priority list of columns to sort on "2,1" "7" etc
 i = Start
 j = Finish
 dim temp$(numCol)

 'create the compare string
 r=int((i+j)/2)
 compa$=""
 o=1
 o$=word$(order$,o,",")
 while o$<>""
   compa$=compa$+dbf$(r,val(o$))
   o=o+1
   o$=word$(order$,o,",")
 wend
 while i <= j
     'create the string to compare against
     compb$=""
     o=1
     o$=word$(order$,o,",")
     while o$<>""
       compb$=compb$+dbf$(i,val(o$))
       o=o+1
       o$=word$(order$,o,",")
     wend
     while compb$ < compa$
       i = i + 1
       compb$=""
       o=1
       o$=word$(order$,o,",")
       while o$<>""
           compb$=compb$+dbf$(i,val(o$))
           o=o+1
           o$=word$(order$,o,",")
       wend
   wend
   'create the string to compare against
   compb$=""
   o=1
   o$=word$(order$,o,",")
   while o$<>""
       compb$=compb$+dbf$(j,val(o$))
       o=o+1
       o$=word$(order$,o,",")
   wend
   while compb$ > compa$
     j = j - 1
     compb$=""
     o=1
     o$=word$(order$,o,",")
     while o$<>""
       compb$=compb$+dbf$(j,val(o$))
       o=o+1
       o$=word$(order$,o,",")
     wend
   wend
   if i <= j then
       for p=0 to numCol
           temp$(p)=dbf$(i,p)
       next
       'a$ = sa$(i)
       for p=0 to numCol
           dbf$(i,p)=dbf$(j,p)
       next
       'sa$(i) = sa$(j)
       for p=0 to numCol
           dbf$(j,p)=temp$(p)
       next
       'sa$(j) = a$
       i = i + 1
       j = j - 1
   end if
 wend
 if j > Start then call qsort Start, j, numCol, order$
 if i < Finish then call qsort i, Finish, numCol, order$
end sub




[tsh73]

Well, qsort is nice bit bubble sort is only 5 lines.
And for small N (up to 25) it works just as fast
(actually if I need sort once in a time I could wait a bit longer - especially if "longer" still milliseconds).

Anyway
Wikipedia says simple sorts work faster up to N=50
my tests show that (my variant) or Bubble sort works just as fast as (shipped with JB) Qsort, 2 ms, at N=25
Insertion sort works 2x faster and it works as afast as QSort at N=40 (2-3 ms!)

At N=100 I got Bubble Sort 33 ms, Insertion 20, QSort 7 (actually times differ with different random values)    

But really, 1/30 sec is OK for sorting for me.

(
oh. Interesting. Just paid atention that this Win7 box give me times with ms accuracy - I see 1, 2, ..8 ms.
I am used to XP giving discrete values of 0 and 16 ms
)

Sample run:
N             tBubble       tInsertion    tQSort
15            1             0             1
20            1             1             1
25            2             1             1
30            3             1             2
35            4             3             1
40            5             3             2
45            5             3             3
50            7             4             3
55            9             5             3
60            11            7             3
65            13            7             5
70            14            8             4
75            16            9             5
80            19            12            5
85            22            12            6
90            24            13            5
95            26            14            6
100           29            15            6
--Over--

Testing code:
'Comparing shipped with JB Qsort with bubble sort, insertion sort - time-wise

mainwin 80 'give me 80 columns
print "N","tBubble", "tInsertion", "tQSort"

for MaxSize= 15 to 100 step 5
N=MaxSize

dim a(N)
dim b(N)

dim NumArray(MaxSize)
'print "(Initial array)"

'generate
for i = 1 to N
b(i)=int(rnd(0)*900)+100'-500
next

'prepare
for i = 1 to N
a(i)=b(i)
next

[bubbleSort]
'prepare
for i = 1 to N
a(i)=b(i)
next

t0=time$("ms")
for j=N-1 to 1 step -1 'number of pairs
for i = 1 to j
if a(i)> a(i+1) then tmp=a(i):a(i)=a(i+1):a(i+1)=tmp
next
'gosub [printArr]
next
tBubble=time$("ms")-t0

'----------------
[insertion]
'prepare
for i = 1 to N
a(i)=b(i)
next

t0=time$("ms")
for j=2 to N '1 is sorted, start with 2
i=j
tmp=a(i)
while (tmp<a(i-1)) AND (i>1) 'touches a(0) (so from 0 will not work) but not uses it
a(i)=a(i-1)
i=i-1
wend
a(i)=tmp
next
tInsertion=time$("ms")-t0

'----------------
[testingQSort]
'prepare
for i = 1 to MaxSize
 NumArray(i) = b(i)
next i

t0=time$("ms")
   call QSort 1, MaxSize
tQSort=time$("ms")-t0

print N,tBubble, tInsertion, tQSort
next
print "--Over--"
end

sub QSort Start, Finish
 i = Start
 j = Finish
 x = NumArray(int((i+j)/2))
 while i <= j
   while NumArray(i) < x
     i = i + 1
   wend
   while NumArray(j) > x
     j = j - 1
   wend
   if i <= j then
     a = NumArray(i)
     NumArray(i) = NumArray(j)
     NumArray(j) = a
     i = i + 1
     j = j - 1
   end if
 wend
'  for k = 1 to Finish
'    print NumArray(k); " ";
'  next k
'  print
 if j > Start then call QSort Start, j
 if i < Finish then call QSort i, Finish
end sub