[bmx]AlphaNumSort

Started by TomToad, August 19, 2019, 22:43:55

Previous topic - Next topic

TomToad

Title:AlphaNumSort
Author:TomToad

Description: Sorts an array of strings.  Case insensitive, so "a" comes before "B".  Number strings are sorted by value, so "n2" comes before "n10".  Based on the algorithm by Dave Koelle (DaveKoelle.com/alphanum.html).  My version works with only positive integers. No floating point nor negative numbers.  It also sorts the array in place, so if you need the array in original order, then create a copy first.

Function AlphaNumSort(s:String[])
'call QuickSort
QuickSort(s,0,s.length-1)

Function QuickSort(s:String[],lo:Int,hi:Int)
If lo < hi
Local p:Int = partition(s,lo,hi)
QuickSort(s,lo,p)
QuickSort(s,p+1,hi)
EndIf
End Function

Function partition:Int(s:String[],lo:Int,hi:Int)
Local pivot:String = s[lo+(hi-lo)/2]
Local temp:String
Repeat
While compare(s[lo],pivot) < 0
lo :+ 1
Wend
While compare(s[hi],pivot) > 0
hi :- 1
Wend
If lo >= hi Then Return hi
temp = s[lo]
s[lo] = s[hi]
s[hi] = temp
lo :+ 1
hi :- 1
Forever
End Function

Function compare:Int(s1:String Var, s2:String Var)
Local chunk1:String, chunk2:String, t1:Int, t2:Int, v1:Int, v2:Int, i1:Int = 0, i2:Int = 0

Repeat
chunk1 = GetChunk(s1,t1,i1).ToUpper()
chunk2 = GetChunk(s2,t2,i2).ToUpper()
If chunk1 = "" And chunk2 = "" Then Return 0
If t1 = 0 Or t2 = 0
If chunk1 < chunk2 Then Return -1
If chunk1 > chunk2 Then Return 1
EndIf
If t1 = 1 And t2 = 1
v1 = chunk1.ToInt()
v2 = chunk2.ToInt()
If v1 < v2 Then Return -1
If v1 > v2 Then Return 1
EndIf
Forever

Function GetChunk:String(s:String Var, t:Int Var, index:Int Var)
Local start:Int = index
If index >= s.length Then Return ""
t = s[index] >= 48 And s[index] <= 57
index :+ 1
Repeat
If index >= s.length Then Return s[start..]
If t
If s[index] >= 48 And s[index] <= 57
index :+ 1
Else
Return s[start..index]
EndIf
Else
If s[index] < 48 Or s[index] > 57
index :+ 1
Else
Return s[start..index]
EndIf
EndIf
Forever
End Function
End Function

End Function

'create an array of strings
Local a:String[] = ["1","2","3","10","11","20","aaa","cc","d1d","d2d","d3d","BBB","d10d","d10F","d10h","d04d","D5D"]

'shuffle the array
For Local i:Int = 0 Until a.length
Local j:Int = Rand(0,a.length-1)
Local temp:String = a[i]
a[i] = a[j]
a[j] = temp
Next
'print the shuffled array contents
Print "Shuffled"
For Local i:Int = 0 Until a.length
Print a[i]
Next
Print
'sort the array
AlphaNumSort(a)
'print the sorted results
Print "Sorted"
For Local i:Int = 0 Until a.length
Print a[i]
Next

------------------------------------------------
8 rabbits equals 1 rabbyte.