I have a programming issue with sorting an array.

September 20, 2005 11:17 PM

I have a programming issue with sorting an array.

Yeah, everything I'm trying just isn't working at the moment. I need to generate some ideas to get some lateral thoughts running through my head. Here's my question:

What's the best way to reorder (sort) an array while making sure that elements of equal value stay in the same position? I'm thinking in terms of a top scores list that should keep the earliest score above all others on the list which score the same (e.g. they both score 120 or another equal value). I have code and will post it if anyone thinks they can help. Also, I'm programming in Macromedia Flash and would call myself an intermediate user.

posted by sjvilla79 to computers & internet (10 answers total)

This kind of sort is called "stable". Algorithms courtesy of Wikipedia.
posted by aneel at 11:25 PM on September 20, 2005

The standard answer is to make the function which does the comparison take into account the current array index of the items. That way the elements are never "equal". It seems to me that your thinking is stuck in the "what to do once I've discovered they are equal" frame of mind, I'm suggesting you approach it by making that situation never come up.

I'm more familiar with Laszlo/Javascript usage in Flash, but since Actionscript is so close to Javascript, I think this technique should work for you. I believe you should be able to do this by making a custom "compare" function and passing it to the sort function.
posted by Invoke at 11:27 PM on September 20, 2005

Use array.sort, documented here. You need to write a custom compareFunction that works as follows (assuming you want highest scores first):

return -1 if (A.score > B.score) or (A.score == B.score and A.time < b.time)br>
return 0 if (A.score == B.score and A.time == B.time)

return 1 otherwise
posted by ldenneau at 11:28 PM on September 20, 2005

(Sorry for the crud at the end of the first line; I should learn how to quote code in MeFi.)
posted by ldenneau at 11:32 PM on September 20, 2005

Ugh, actionscript. The language of deamons.

The obvious answer is to sort first by score, then by date, which is ldenneau's code would do. Otherwise, implement the Bubblesort yourself.
posted by delmoi at 11:42 PM on September 20, 2005

aneel's answer is good. But Bubblesort may be slooow, and all the others labeled O(n²) too. Probably a bucket sort is your best bet.

I'm betting that you don't have a computer science background. The O notation indicates the cost in execution time of the algorithm. O(n) says the cost increases linearly with the number of elements. Bubblesort cost increases with the square of the number of elements. The big O notation is discussed later on in the same article aneel linked to. I wouldn't want you to go straight to bubblesort as delmoi suggests unless you are confident your typical data set is small enough for it not to matter.

However, it depends on how many items there are (and the capabilities of your target platform) whether you will notice poor scaling. If you only have to sort a handful of items pick the one that you understand well enough to implement reliably.

Note that all performance for sort algorithms is contingent on the typical distribution of the data too.

Apologies for being patronising if you have already read the article thoroughly or sat through the same kind of classes I did.
posted by i_am_joe's_spleen at 1:48 AM on September 21, 2005

ldenneau's answer is in practice what you want though if you are under any time constraint at all. *kicks self for not thoroughly reading all the answers*

Whenever you are using a scripting language, odds are that the native sort is implemented using the C library quicksort implementation, and it will be very quick.
posted by i_am_joe's_spleen at 1:52 AM on September 21, 2005

the above are correct - you want a stable sort and can fake that by including indices in your comparison function.

Yes, bubblesort is O(n^2) in the worst case (input is in reverse order). However, it approaches O(n) for input data that is already sorted or very nearly so. In such a case it can be faster than quicksort which will still be O(n log n). But that difference won't be available until you hit very large datasets and the two sorts are implemented in the same language.

So just do what ldenneau said :)
posted by polyglot at 3:43 AM on September 21, 2005

Thanks everyone for your feedback. I've got enough here to start thinking differently about the task ahead. Hopefully I'll get to tackle this all tomorrow sometime. Cheers again.

Yeah, I'll post back and review answers again when I'm sorted. Pardon the pun!
posted by sjvilla79 at 6:16 AM on September 21, 2005

Got it working and all is well. Cheers again for the help.
posted by sjvilla79 at 11:51 PM on September 22, 2005