Friday, 25 September 2009

Sorting Numeric Arrays with Actionscript

Just lately I have been having fun with arrays. Of course, I say "having fun", what I mean is having problems. Especially with sorting numerically.

Arrays are really useful, they allow you to store data, select data, order it, etc. You can create them from strings and other variables, and turn them into strings and other variables. All in all, they can be very handy.

I found them handy as part of a game I was writing a couple of days ago. As part of my code I needed to find the number with the highest value out of a choice of 3 numbers. The logical solution was to put all 3 numbers into an array, then sort them numerically, then retrieve the last item in the array (this should, after sorting, be the one with the highest value).

Numeric sorting is not numeric

Let's say we start with the following array:

var my_array:Array = [650,12,86];

Then we sort them numerically:

my_array.sort(Array.NUMERIC); //doesn't work correctly

After this command you might expect flash to order the array as:

12, 86, 650

But what you actually get is:

12, 650, 86

This is because, as the Flash documentation explains, 'Numeric fields are sorted as if they were strings, so 100 precedes 99, because “1” is a lower string value than “9”. '

In other words, the Numeric sort does not sort numerically at all. It sorts alphabetically. Odd sort of numeric, but it can't be helped, we have to find a solution.

Prepending 0s so all values have the same number of digits

Of course this only happens because not all the values had the same number of digits. If the lower values began with a 0 then a numeric (alphabetical) sort would work correctly. So my initial plan was to use an if statement in a for loop to check for 1 digit, 2 digit and 3 digit numbers and prepend (put in front) 0s to make them all the same number of digits as follows:

for (var i = 0; i<finalscores_array.length; i++) {

if (finalscores_array[i]<=9) {

finalscores_array[i] = "000"+finalscores_array[i];

} else if (finalscores_array[i]<=99) {

finalscores_array[i] = "00"+finalscores_array[i];

} else if (finalscores_array[i]<=999) {

finalscores_array[i] = "0"+finalscores_array[i];

} else {

finalscores_array[i] = finalscores_array[i];



With for loops we can repeat a peice of code until a condition is met. This loop repeats for the length of the array (that's the number of items in the array). It starts by checking how many digits the first array item has. Then depending on how many digits the code prepends 3, 2, 1 or no 0s. On the next repetition it checks the next array item, and so on until all array items have been checked and had the required number of 0s prepended so that they all have the same number of digits, and then the loop ends.

The result is that the original values:

650, 12, 86


0650, 0012, 0086.

Now when we sort them numerically, it does put them in the right order:

0012, 0086, 0650.

Leading 0s alter the value (it's a decimal v. octal thing)

Wouldn't it be great if that was the end of your troubles?

The problem is that if we then want to do anything with the values afterwards, like doing anything other than displaying them, we need to remove the 0s we just added. And it is not nearly as easy taking off, as putting on.

The reason we have to remove the leading 0s is because Flash, like lots of other programs, does not treat numbers beginning with 0 as decimal numbers. It treats them as octal. This means that 0650 does not have the same value as plain old 650 (without the leading 0).

0650, as octal, actually has the decimal value of 424.

0650 is in fact a totally different number to 650.

So while prepending leading 0s solves our array sorting problem, it actually changes our values. just because a leading 0 in Flash means it is an octal value, not a decimal value.

Leading 0.0 do not alter the value (it's a less than 1 thing)

But then I realised. Hang on a minute says I (yes, programming problems really can have you doing a good Ben Gunn impression). Hang on a minute says I, Flash handles numbers begining with a 0 all the time. What about 0.1, 0.2 etc. It has no problems with decimal values of less than 1.

And here is my solution. Instead of using my for loop to prepend just 0s, I will use it to prepend 0.0s, as follows:

for (var i = 0; i<finalscores_array.length; i++) {

if (finalscores_array[i]<=9) {

finalscores_array[i] = "0.000"+finalscores_array[i];

} else if (finalscores_array[i]<=99) {

finalscores_array[i] = "0.00"+finalscores_array[i];

} else if (finalscores_array[i]<=999) {

finalscores_array[i] = "0.0"+finalscores_array[i];

} else {

finalscores_array[i] = "0."+finalscores_array[i];



The result is that the original values:

650, 12, 86


0.0650, 0.0012, 0.0086.

Now when we sort them numerically:


It does put them in the right order:

0.0012, 0.0086, 0.0650.

OK, I know that doing this has changed the values too, but at least they are still decimals (not a totally different numbering base). Because they are still decimals it is easily rectified, it's just a case of shifting the decimal point a few places. And we can do this by very simple multiplication...

...just multiply them by 10,000.

0.0012 x 10000 = 12
0.0086 x 10000 = 86
0.0650 x 10000 = 650

So, to finish off, now we have prepended 0.0s to our original values, then sorted them, all I need to do to get the highest value is retrieve the last item from the array, and multiply it by 10000.

var highestscore:Number = (my_array[my_array.length-1])*10000;

The Faster Way

Having made this wonderful discovery, it is good to know that all the code required to debug and investigate the problem is not necessarily needed to apply the solution. Pre-pending using the IF and ELSE IF is only necessary if you want to pre-pend digits to a String (as in converting 650 to 0650). Now that we have discovered that only decimals (as in 0.650) will sort correctly there is a much simpler way to achieve this.

Simply - divide the original number by 10000 (after all, we convert them back by multiplying them by 10000).

for (var i = 0; i<finalscores_array.length; i++) {

finalscores_array[i] = finalscores_array[i] / 10000;

I count that as 7 lines fewer code, than the pre-pending method.

That's the difference between what we do to understand a problem and what we do to apply a solution.

And there we have it. Hopefully some of you will find this helpful. Frankly I don't know why numeric sorting doesn't just work. But since it doesn't, here is a cheap and cheerful workaround - in summary:

1. Divide them all by 10000 (so that every number begins "0.")
2. Sort them
3. Multiply them all by 10000 (so you get the original values back)

Happy sorting.

No comments:

Post a Comment