AS2 Sorting Algorithms
February 27th, 2006
I’ve come across various sorting algorithms a few times and have wanted to see how they perform in Flash. Recently I came across this list of algorithms and thought I’d finally play around with them.
The above sorting functions were written in java so I converted them to actionscript and created a test swf below. Create a test array by entering a number, say 1000 for example, then run a sort on the array. The array that’s generated consists of random numbers between 1 - 250 and the sorting algorithms sort the array from lowest to highest. Note, I didn’t include the Quick Sort algorithm because its too recursive and Flash complains. It’s not as quick as some of the other algorithms anyway so no big loss. I also had to grab the Shell Sort from Wikipedia since the one I found above goes into an endless while loop. Typo in the example or just a bad conversion on my part, I’m not sure.
Overall the Insertion Sort seems to be the most efficient. I’ve included the source code for the sorting algorithms here:
Sorting.zip
I’m going to play around with these some more and make some modifications to the class so that you can pass in more complex arrays and specify which property you’d like to sort by, add ascending vs descending, etc.
UPDATE:
The following code example was posted by Felix, it just didn’t make it in the comment form.
var i:Number = 0;
var n:Number = ar.length;
var tmp;
while (i < n) {
if (i == 0 || ar[i-1] <= ar[i]) {
i++;
} else {
tmp = ar[i];
ar[i] = ar[i-1];
ar[–i] = tmp;
}
}
}
Currently residing in Scituate, MA and working at 
February 27th, 2006 at 10:06 am
You might be interested in the custom array sort algorithm that I wrote. I tweaked the bin sort to create a very rapid way to sort integers in Flash:
http://www.darronschall.com/weblog/archives/000069.cfm
In practice, it’s probably not a good idea to use the sorts that you mention. These are the classic sorts that are taught in introductory computer science, but they are generally not fast enough, especially in ActionScript. It’s probably better to rely on the internal Array sort method because it’s the quick sort algorithm and it executes at C++ speed since it’s native to the Flash Player.
February 27th, 2006 at 10:14 am
Thanks for the input. The reason for creating these was mostly out of my own curiosity as to how each would perform in flash. I unfortunately missed this part of intro comp sci being a biology major
February 27th, 2006 at 10:59 am
More important than the implementation details, then, is the understanding of what the sort themselves are doing. Have you had a chance to look at any of the “visual” sort demos on the internet? They show the sort “in progress” to help understand the key differences between the sorts:
Here’s one:
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
Here’s another:
http://math.hws.edu/TMCM/java/xSortLab/
Why not try making one in Flash to help in your understanding of the sorts as a learning tool?
February 27th, 2006 at 11:07 am
I started working on a visual sort but hadn’t finished it yet. Thanks for the links. I’ve seen the first one a long time ago. The second one makes it pretty clear what’s going on during the sort.
February 27th, 2006 at 1:04 pm
I’ve seen some of those links before and wondered if it would be worth implementing some of the faster methods in AS. Makes sense though, that the built in one would be faster.
February 27th, 2006 at 4:29 pm
Hey tim,
here’s another one you could include in your benchmark: It’s called “gnome sort” (http://www.cs.vu.nl/~dick/gnomesort.html). An as version would be something like this: (I’m guessing gnome sort is quite slow compared to the others…?)
function gnomeSort(ar:Array):Void {
var i:Number = 0;
var n:Number = ar.length;
var tmp;
while (i
February 27th, 2006 at 4:31 pm
sorry…the blog software cut off my post…? some illegal chars…?
@darron: sounds reansonable that the internal Array.sort method should be faster but some time ago I compared it with a custom quick sort function and if I remember correctly in some cases the quick sort was faster than Array.sort…
February 28th, 2006 at 3:28 am
[...] Interessante articolo riguardante gli algoritmi di ordinamento (i più famosi) che in questo caso interagiscono con gli elementi di un array (la quale cardinalità è a discrezione dell’utente). Come dice l’autore il QuickSort non ha potuto implementarlo perchè l’albero delle ricorsioni di Flash è piuttosto limitato (se non erro si limita a 256 chiamate ricorsive). [...]
April 13th, 2006 at 9:08 pm
[...] Several Sorting Algorithms [...]