QuickSort for GameMaker

Some time ago I made BogoSort for GameMaker, which is a sorting algorithm that you should never run because you (and your descendants, and probably the entire Solar System) will die before it completes. QuickSort is the opposite: it's a sorting algorithm that's actually good!

Performance

As the name implies, it's rather fast. QuickSort has a best- and average-case performance of O(nlog(n)) and a worst-case performance of O(n²), which is pretty good, as far as general-purpose list sorting goes. However, this being GameMaker, of course that's not the end of the story performance-wise.

GameMaker has array_sort and ds_list_sort built-in. As it turns out, these are pretty fast. It's not that they use a faster sorting algorithm than O(nlog(n)), but because - and if you've been using GameMaker for an extended period of time, you probably have a pretty good idea about why - GML is a slow language. The built-in sorting functions run in native code, which will always outperform the same operation written in GML by a large margin (even on the YYC).

If you need to sort a simple list or array of numbers or strings, you should always, always, always use the built-in functions.

However, there are some cases where this is not an option. If you want to sort something that isn't a number or string (e.g. a struct), or if you want to sort something based on a criteria other than simply what value is greater, you have to write your own - and this can be very slow indeed. This is where having an efficient sorting algorithm can come in handy.

See the included tests for examples:

• Sort numbers by value (not recommended in practice)
• Sort colors by hue
• Sort first and last names, by last name

This should be obvious, but the YYC speeds this function up considerably.

What about MergeSort?

Some of you computer science nerds may also be familiar with Merge Sort, which is another efficient sorting algorithm which may perform similarly to QuickSort. I may someday implement Merge Sort, but I have a feeling it won't perform nearly as well in GML as QuickSort, due to how slow allocating arrays in GML is.

Documentation

The quicksort function takes either a list or array (doesn't matter) and sorts it. The compare function should take two arguments (elements in the list or array) and return 1 if the first element is lesser, -1 if the first element is greater, and 0 if the two elements are equal. A simple comparison function to sort a list of values in order would be:

function(a, b) {
    return a < b;
}

See the quicksort_tests for examples of other compare functions.

Price

My standard disclaimer of

As usual, the asset is free as-is. I'll fix simple or game-breaking bugs but more involved support requires payment via either Itch or Patreon.  I get the final say in what constitutes "game-breaking."

applies, as usual, although I have a feeling I won't be doing anything else with this code. It passes all my tests and I'm not interested in doing anything else to it.

Credits

• Icon is run by Alena from the Noun Project