-
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...
3 Comments
Hai zevan..
nice article…
cheers from malaysia..
sorry for my bad english
omg, what a complicated way to such an asy thing like sortOn :))))
Check out my method which WAAAAyyy more easier.
http://chargedweb.com/labs/2010/02/20/vector-sorton/
its not that bad… lots of more complicated versions that are faster… turns out nothing is faster than Array.sort() though