Comb Sort for strings

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

A fast sort routine. This scored best overall in a comparison test of MMBasic sorts (but the CSub routines are at least 3x faster).

originally published http://www.thebackshed.com/forum/forum_posts.asp?TID=7311&TPN=3 and tweaked slightly for MMBasic syntax

One advantage of a purely MMBasic sort is it can be modified e.g. to sort an array but to maintain index links in another, so as you swap compared elements of the array, you swap their index references too.

Credit: twofingers

' Comb Sort
' an optimized (8/2017 by twofingers@TBS) version of aCombSort for strings.
' It sorts the array S$() and needs the number of elements to sort (STop)
' Usage: CombSort STop
'
' It takes 330ms (or less) for an array of 100 elements
' System: MM2/48MHz/MMBasic 5.04.05
'
Sub CombSort(STop)
Local string M$
Local integer i, h, T=1, F=0, sw
Local float Gap=STop, 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 STop
    If S$(i)>S$(h) Then
       M$=S$(i):S$(i)=S$(h):S$(h)=M$:Sw=T
    EndIf
    i=i+1
  Next
Loop
End Sub