Need to sort an Array? No sweat, Array's have a built-in "sort" method. You decide to call my_array.sort() only to find out your numbers aren't sorted correctly. You build a custom comparison function to pass into sort only to realize that sorting 3000 numbers takes 261 milliseconds. What the heck?
We all know that the built-in Array sort method isn't the fastest around. The best way around the speed issue is to either build your own sorting method, or use someone else's. Prototype is a good place to start looking for code, and now you've brought that 261 milliseconds down to 127 with the qSort method, and even further down to 103 milliseconds with sortPInt. Still, I can't help but think that we can do better...
So.. thinking a bit about the problem, I've come up with my own custom sort method. At it's heart it resembles the "Bin Sort" algorithm. I was able to reduce the sorting time down to 58 milliseconds (from the original 261). Sweetness.
For starters, this sort method was built for a project I'm working on and thus only functions correctly under a given set of conditions. There are really only 2 conditions that need to be met for this sort to work.
- All of the array elements must be integers (no decimals!) - positive and negative integers will both work
- The theoretical min and max values of the elements inside the array must be known
If those conditions aren't met, then don't expect correct sorting results using my custom sort method. It's ok if the values you supply aren't the actual min and max values contained in the array - they only need to be the theoretical min and mix. But, the closer they are to the actual values the better performance you will see.
To start off, here is the code I'm using to test. What this does is generate an array of 1000 integers, ranging from -1005 to 1994. Where did these numbers come from? Why, I made them up for this example of course!
range = 3000;
min = -1005;
max = min + range - 1 // 1994
// create the numbers array and populate it
numbers = new Array(1000);
for (var i = 0; i < 1000; i++) {
numbers[i] = Math.floor(Math.random() * range) + min;
}
Note that declaring the array a fixed size and adding elements with the [] operator is faster (in this case, at least) than declaring a dynamic array (numbers = new Array()) and adding elements with "push" (numbers.push(newElement)). How much faster? Well, the dynamic array takes my computer around 51 milliseconds to build, whereas the fixed-length array takes only 45. This isn't a huge difference, but sometimes every little bit counts. Plus - Since we know we're going to have 1000 elements, why would we make the array dynamic anyway? That's a rhetorical question, for the most part.
Next comes testing the built in sort method. Here we go:
// assuming numbers is built like the code snippet above
start_t = getTimer();
numbers.sort();
trace("time: " + (getTimer() - start_t) + " ms");
trace(numbers);
With the above code snippet, you can see that the numbers aren't sorted correctly. Flash thinks that we're trying to sort strings instead of numbers (for example, 1403 comes before 304 because 1 is less than 3). So, we build a custom comparison function and run the test again:
function numCompare(a, b) {
if (a < b) return -1
if (a == b) return 0;
return 1;
}
start_t = getTimer();
numbers.sort(numCompare);
trace("time: " + (getTimer() - start_t) + " ms");
trace(numbers);
That's better... but by golly that beast is slow. At least we got correct results this time, but let's see what we can do to improve the sort time.
I repeated the same testing process for those 2 prototypes mentioned in the opening paragraph....
Copy the Array.prototype.qSort method to the frame replace "numbers.sort(numCompare)" with "numbers.qSort(0, numbers.length-1)" - this is faster, but not fast enough.
Trying again.. copy the sortPInt method to the frame, and change the sorting line to "numbers.sortPInt()" - again, a little bit faster, but still not quite fast enough. Note that this sort only takes positive integers, so you'll need to change the min value to a positive integer for the sort to work correctly.
Finally, get fed up and write your own custom sort method. Copy the code below, and then replace the sort call with "numbers.customSort(min, max)". Min is the smallest possible value in the array, and max is the largest possible value in the array. Note that these variables were defined right about the for loop that populates the numbers array. Also note that these are the theoretical min and max.. and may not actually be the min and max elements contained in the array.
// Darron Schall
// 11/07/03
// pre: min and max are the theoretical min and max values
// contained in the array. the array contains only integers.
// post: the array will be sorted in ascending order
Array.prototype.customSort = function(min, max) {
var i;
var bins = new Array(max-min+1);
var binvalue;
// distribute array to bins
i = this.length;
while (i--) {
binvalue = this[i]-min;
if (bins[binvalue] == undefined) {
bins[binvalue] = 0;
}
bins[binvalue]++;
}
// rebuild - this may see some speed gains
// by making the array fixed-length instead
// of dynamic
var tmp = new Array();
i = bins.length;
while (i--) {
if (bins[i] != undefined) {
while (bins[i]--) {
tmp.push(i);
}
}
}
// reconstruct this from tmp, reversing the order
i = this.length;
while(i--) {
this[this.length-i-1] = tmp[i]+min;
}
}
As stated before, my customSort method takes only 58 milliseconds to execute on my computer. Considering the built-in method takes 261 milliseconds, I would call this sort algorithm a success in this scenario. Of course, my custom sort may not always be the fastest depending on the number of elements in the Array. It seems to really outperform when the integer array to sort is large.
Read on for an explanation of my algorithm...
