Page History: Shell Sort
Compare Page Revisions
Page Revision: 2016/12/23 23:14
For completeness, below is an MMBasic version of a Shell sort - it is about four to five times faster than a bubble sort but does have a serious caveat in that it can fail if the data is in an unfortunate order - this is just a fact of life for Shell sort. That said, it is very unlikely to happen but be warned.
For speed you are better off choosing the
Cube Root of Two Sort, it beats a shell sort (100 strings in a third of a second) and doesn't suffer from a mal-sort on certain data combinations.
Example:
Option Base 0
Dim xx As Integer
xx=my_arraysize 'lack of UBOUND() means we have to manually track the array size
Dim SP$(xx)
ShellSort xx
:
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 sort balancing value
END IF
WEND
END SUB