Vector.sortOn()

var a:Vector.<Sprite> = new Vector.<Sprite>();

trace("unsorted");
for (var i:int = 0; i<10; i++){
	var s:Sprite = new Sprite();
	s.x = int(Math.random()*100);
	a.push(s);
	trace(s.x);
}

quickSortOn(a, "x", 0, a.length-1);

trace("sorted");
for (i= 0; i<10; i++){
	trace(a[i].x);
}

// modified code from kirupa.com
// http://www.kirupa.com/developer/actionscript/quickSort.htm
function quickSortOn(a:Vector.<Sprite>, prop:String, left:int, right:int):void {
    var i:int = 0, j:int = 0, pivot:Sprite, tmp:Sprite;
	i=left;
	j=right;
	pivot = a[Math.round((left+right)*.5)];
	while (i<=j) {
		while (a[i][prop]<pivot[prop]) i++;
		while (a[j][prop]>pivot[prop]) j--;
		if (i<=j) {
			tmp=a[i];
			a[i]=a[j];
			i++;
			a[j]=tmp;
			j--;
		}
	}
	if (left<j)  quickSortOn(a, prop, left, j);
	if (i<right) quickSortOn(a, prop, i, right);
}
/* outputs something like:
unsorted
26
33
20
63
7
68
75
39
67
53
sorted
7
20
26
33
39
53
63
67
68
75
*/

This demo is my first quick stab at using at a sortOn() function for the Vector class. It sorts a Vector of Sprites by their x property.

Recently there were a few times when I was prototyping ideas and suddenly realized that I needed to change my Vector to an Array because I needed to use sortOn().(If you don’t already know, there is no built in sortOn() method for the Vector class). In the past I spent some time with sorting algorithms, bubble, insertion etc… so I knew I could pretty easily write my own sortOn(), but I also realized that a generic implementation wouldn’t be easy/possible without loosing the type of the Vector. What I mean is, if you have a Vector of Sprites, you need a sorting method that takes a Vector.< Sprite > type as an argument (as seen above), if you have a Vector of TextFields you need a Vector.< TextField > type as an argument. You could of course use a generic type, but this kind of defeats the purpose of using a vector in the first place…

I will likely post a revised version of this in the near future with a slightly improved implementation of QuickSort. I haven’t spent that much time with this, but If I recall correctly this is not the ideal implementation. I ported this code from a nice Kirupa tutorial and modified it to sort based on a property…