Generic quicksort?

Monkey Forums/Monkey Programming/Generic quicksort?

Nobuyuki

(Posted 2012) [#1]

Hey, just a quick question. If it is possible, has anyone written for monkey a function which can iterate through a set (perhaps a List<Object>) of objects and quicksort them by one of its members in a generic fashion? I've heard that request made of some of the built-in collections before, to have some sort of a .Sort(member, eval) thing going on, or a sorted copy, but I don't know if anyone's actually implemented it.

Perhaps Diddy's ArrayList has this? It doesn't appear you can use ArrayList easily without diddy, though...

For my purposes, I was thinking about this mainly because doing things like Z-Order render sorts and object size comparison sorts (to render similar objects in a list in order by the image they use so as to speed up blitting), and I haven't yet explored porting quicksort (or stealing an existing port) myself. I'm afraid I flunked out of the sorting algorithms portion of learning how to code, so I figured it wouldn't hurt to ask about the state of that in the community :)

DruggedBunny

(Posted 2012) [#2]

I don't know if this helps at all, but I don't think we can do it generically (ie. passing arbitrary object types/fields to a function) without reflection in Monkey.

Class Example
	Field y:Int
End

Class ExampleList Extends List <Example>
	Method Compare:Int (e1:Example, e2:Example)
		Return e1.y > e2.y
	End Method
End

Function Main ()

	Local test:ExampleList = New ExampleList
	
	' Add some example objects with y values...
	
	For Local loop:Int = 0 Until 100
		Local e:Example = New Example
		e.y = Rnd (100)
		test.AddLast e
	Next
	
	' Sort
	
	test.Sort
	
	For Local e:Example = Eachin test
		Print e.y
	next
	
End

AdamRedwoods

(Posted 2012) [#3]

It is undocumented, but as mentioned above, List<> has a sort method. You can use it by extending the List<> class.

The above example is good-- but (correct me if I'm wrong) you may need to return 3 values for Sort(): 0,1,-1 for equal,greater than, and less than (respectively).

ie

Class ExampleList Extends List <Example>
	Method Compare:Int (e1:Example, e2:Example)
		If e1.y < e2.y Then Return -1
		Return e1.y > e2.y
	End Method
End

I use it to Z-Order in miniB3D, and UNFORTUNATELY monkey cannot radix-sort.

Samah

(Posted 2012) [#4]

ArrayList can indeed do exactly what you're after, and the only dependency is the assert module. You can easily remove the assert calls too if you dont want them.

Instructions and code samples here:
http://code.google.com/p/diddy/wiki/ArrayList

DruggedBunny

(Posted 2012) [#5]

@AdamRedwoods: You're probably right there -- I think I took this from a BlitzMax example long ago.

matty

(Posted 2012) [#6]

For zordering, I usually use a sort method that simply uses an array of height = the screen height and then create a list at each array element containing the list of image references to draw at that y-coordinate, then simply run through the array in sequence (0-height-1) and it is already sorted!

Samah

(Posted 2012) [#7]

Modified version of DruggedBunny's example, using ArrayList and the IComparable interface.

Import diddy.collections

Class Example Implements IComparable
  Field y:Int
  
  Method Compare:Int(o:Object)
    Return y - Example(o).y
  End

  Method Equals:Bool(o:Object)
    Return o = Self Or y = Example(o).y
  End
End

Function Main ()
  Local test:ArrayList<Example> = New ArrayList<Example>
	
  ' Add some example objects with y values...
	For Local loop:Int = 0 Until 100
    Local e:Example = New Example
    e.y = Rnd (100)
    test.Add(e)
  Next

  ' Sort
  test.Sort

  For Local e:Example = EachIn test
    Print e.y
  Next
End

Disclaimer: Typed in Notepad++, hopefully it compiles. ;)