Sorting an array

Hey Glenn,

I was just wrestling with a very similar problem. Here's an example I built, inspired by JazzieB's example and a couple others that were posted in different threads. It shows a user-defined record type which has a first name, a last name, and a score, and can be sorted in multiple ways, including last-name-then-first-name.

Sorting a TList is much slower than sorting an array if the list is very large, because of the nature of lists. Basically, the time taken is proportional to the square of the number of records. On my computer, 1,000 records take 1/20 second, but 30,000 records take 45 seconds.

' by Kibo -- this code is released into the public domain

SuperStrict

Const NUM :Int = 5000 ' number of records to sort

Global PersonsList :TList = New TList ' list of all the records

Local a :Int ' loop variable, for counting records
Local b :Int ' loop variable, for counting letters
Local p :TPerson ' the record we're working with
Local t1 :Int ' time before the sort
Local t2 :Int ' time after the sort

For a = 1 To NUM
	p = New TPerson ' create a blank record
	p.score = Rand(1, 100000) ' random scores
	For b = 1 To Rand(2, 5)
		p.firstname :+ Chr(Rand(65,90)) ' random first name
	Next ' b
	For b = 1 To Rand(2, 8)
		p.lastname :+ Chr(Rand(65,90)) ' random last name
	Next ' b
	PersonsList.addlast(p) ' save the record
Next ' a

Print "Working..."
t1 = MilliSecs()

' these two lines do the actual sorting
SetFileSortMode(SORT_LAST_NAME_THEN_FIRST_NAME)
SortList(PersonsList, True) ' True = ascending order

t2 = MilliSecs() - t1

a = 0
For p = EachIn PersonsList
	a :+ 1
	Print "#" + a + ": " + p.score + " " + p.firstname + " " + p.lastname
	If a > 50 Then Exit
Next

Print "Finished sorting " + NUM + " records in " + t2 + " milliseconds."

End

''''''''''''''''''

' The different methods supported for sorting our records.
' You must do SetFileSortMode(something) before you can sort.
Const SORT_SCORE                     :Int = 1
Const SORT_LAST_NAME                 :Int = 2
Const SORT_LAST_NAME_THEN_FIRST_NAME :Int = 3

' Set the current sorting mode.
Function SetFileSortMode( m :Int = SORT_SCORE )
	TPerson._sortmode = m
End Function

''''''''''''''''''

Type TPerson

	Global _sortmode :Int ' too bad BlitzMax doesn't have ":Enum"

	Field firstname  :String = ""
	Field lastname   :String = ""
	Field score      :Int    = 0
	
	' Compare is the method called by SortList for every pair of records.
	Method Compare :Int (o2 :Object) ' Compare() is always passed an Object...
		Local p2 :TPerson = TPerson(o2) ' ...convert Object to our type to use it
		Local c :Int ' scratch variable for intermediate comparison
		
		Select _sortmode
			Case SORT_SCORE
				' for ints or floats, subtract #2 from #1
				Return self.score - p2.score 
			Case SORT_LAST_NAME
				' for strings, call the string Compare method
				Return self.lastname.Compare(p2.lastname) 
			Case SORT_LAST_NAME_THEN_FIRST_NAME
				' compare last names and if there's a tie, compare first names
				c = self.lastname.Compare(p2.lastname) 
				If c = 0 Then c = self.firstname.Compare(p2.firstname)
				Return c
			Default
				RuntimeError("Bad sorting method '" + _sortmode + "' in TPerson.Compare().")
		End Select
	End Method
	
End Type ' TPerson