Shell Sort

Modified on 2017/08/11 21:37 by CaptainBoing — Categorized as: Arrays, Maths, Sort, Strings

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.

Before choosing a sort algorithm, read this article.

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

ShellSort:


  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