Array sorting 101

BlitzMax Forums/BlitzMax Programming/Array sorting 101

Tachyon

(Posted 2008) [#1]

I have an elementary problem, caused mostly from the lack of documentation in BlitzMax....

I am trying to sort an array of objects by a field. Here is a sample code:

SuperStrict

Type TCar
    Field color:String
    Field model:String
End Type

Local Car:TCar[100]

For Local n:Int = 0 To 99
    Car[n] = New TCar
    Select Rand(5)
        Case 1 Car[n].color = "Red"
        Case 2 Car[n].color = "Green"
        Case 3 Car[n].color = "Blue"
        Case 4 Car[n].color = "Purple"
        Case 5 Car[n].color = "White"
    End Select
    Print Car[n].color
Next

Print "Sorting by color...."

Car.Sort()  '<-- Obviously, this doesn't work...I need to specify the .color

For Local n:Int = 0 To 99
    Print Car[n].color
Next

Am I using .sort() correctly?

plash

(Posted 2008) [#2]

SuperStrict

Type TCar
	Field i_color:Int
	Field color:String
	Field model:String
		
		Method SetColorByInt(i_c:Int)
		
		  i_color = i_c
			
			 Select i_color
			        Case 1 color = "Red"
			        Case 2 color = "Green"
			        Case 3 color = "Blue"
			        Case 4 color = "Purple"
			        Case 5 color = "White"
   			 End Select
			
		End Method
		
		Function SortCarsByColor(A:TCar[])
			Local swapped:Int = True, i:Int, j:TCar
			
			While swapped = True
				
				swapped = False
				
				For i = 0 To A.length - 2
					
					If A[i].i_color > A[i + 1].i_color
						
						j = A[i]
						
						'swap
						A[i] = A[i + 1]
						A[i + 1] = j
						
						swapped = True
						
					End If
					
				Next
				
			Wend
			
		End Function
		
End Type

Local Car:TCar[100]

For Local n:Int = 0 To 99

    Car[n] = New TCar
	Car[n].SetColorByInt(Rand(5))

Next

Print "Sorting by color...."

TCar.SortCarsByColor(Car)

For Local n:Int = 0 To 99
	
	Print Car[n].color + "~t" + Car[n].i_color
	
Next

BubbleSort!

kfprimm

(Posted 2008) [#3]

Method Compare:Int(withObject:Object)
	Local other:TCar=TCar(withObject)
	If other=Self Return 0
	If other<>Null
		Local clr1$=color.ToLower()
		Local clr2$=other.color.ToLower()
		For Local i:Int=0 To Min(clr1.length,clr2.length)-1
			If clr1[i]=clr2[i] Continue
			If clr1[i]>clr2[i] Return 1
			Return -1
		Next
		If clr1.length=clr2.length Return 0
		If clr1.length>clr2.length Return 1
		Return -1
	Else
		Return 1
	EndIf
End Method

Add this to TCar.
Look under Language->Objects for the documentation on the Compare method. I actually had no idea that Sort() was an array method until I saw that example.

jsp	(Posted 2008) [#4]

Or something like this:

SuperStrict

Type TCar
    Field color:String
    Field model:String

	Method Compare:Int(other:Object)
		Local obj:TCar	= TCar(other)
		If obj	= Self		Return 0
		If color > obj.color
			Return 1
		End If
		Return -1
	End Method

End Type

Local Car:TCar[100]

For Local n:Int = 0 To 99
    Car[n] = New TCar
    Select Rand(5)
        Case 1 Car[n].color = "Red"
        Case 2 Car[n].color = "Green"
        Case 3 Car[n].color = "Blue"
        Case 4 Car[n].color = "Purple"
        Case 5 Car[n].color = "White"
    End Select
    Print Car[n].color
Next

Print "Sorting by color...."

Car.Sort()  '<-- Obviously, this doesn't work...I need to specify the .color

For Local n:Int = 0 To 99
    Print Car[n].color
Next

Czar Flavius

(Posted 2008) [#5]

BUBBLE SORT IS EVIL. DO NOT USE IT.

It is slow and there are faster algorithms available that are still simple.

plash

(Posted 2008) [#6]

Doesn't array.Sort() use the bubblesort algorithm?

Brucey

(Posted 2008) [#7]

No, it uses Quicksort :-p

Tachyon

(Posted 2008) [#8]

jsp: your example works just fine, but I don't understand what is going on! You never actually call the Compare method, so how does this work??

plash

(Posted 2008) [#9]

It's internal, the Sort method calls Compare to figure what's supposed to go where.

jsp	(Posted 2008) [#10]

What Plash and Khomy Prime said.

From the docs:
Compare:Int( otherObject:Object )
Returns a value less than 0 if an object is less than another object,
a value greater than 0 if an object is greater than another object or
the value 0 if an object equals another object.

Otus	(Posted 2008) [#11]

The compare method jsp provided is correct otherwise, but when color=obj.color it should either return 0 or compare another field. Not that it matters much with sorting, but things like this can cause annoying bugs later on.

jsp	(Posted 2008) [#12]

Right, it's not that important for the sort here, but a good point as Tachyon may want to add a sub-sort on the TCar.model, depending on the output he is looking for. Returning 0 could also be faster in a huge array as you could save one swap in the quicksort, but i guess that's just minor.