It seems that I keep on implementing small projects into CI lately. Today I've written a small universal Heapsort function. Wikipedia has a pretty useful article (for once!): http://en.wikipedia.org/wiki/Heapsor... In short, it's an efficient comparative sorting algorithm.
What's special is that I wrote the Heapsort function with auxiliary HeapsortCompare function such that you can sort arrays in any way you like. Just change the code in HeapsortCompare, no matter what types you are comparing, and the Heapsort function will still perform. Here's a simple showcase:
I chose Heapsort because it's the only O(n log n) in-place sorting algorithm I know of. What's nice is that this is also the worst-case time complexity despite taking O(1) space.
So... merge sort is not in-place I guess? Because, I thought merge sort took O(n log n) time too.----------------- 3.14159265358979323846264338327950288... Nothing Here
It is indeed O(n log n), but due to its process of merging, the space complexity is at worst O(n) and requires usually up to n/2 memory to implement. But it seems that there are some papers with an improvement that brings its space complexity to O(1): http://citeseerx.ist.psu.edu/viewdoc...
Right now I'm actually using Wikipedia to see if I can find an algorithm I like better than Heapsort: http://en.wikipedia.org/wiki/Sorting... At the moment I'm interested most in Smooth sort, as it seems not too much work to adapt my implementation.----------------- Hopefully PA is inconsistent.
How can space conplexity by O(1)? You always need at least the length of the array!----------------- 3.14159265358979323846264338327950288... Nothing Here
That's definitely true. In this respect, all sorting algorithms are truly at least O(n) in space complexity. But that's not useful at all when you're trying to compare the memory taken by two sorting algorithms. That's why all of the space complexities I'm talking about are actually the auxiliary space complexities, the 'extra' space required by an algorithm. This includes any space used e.g. for swapping and merging outside of the original array, which is always going to contribute O(n) complexity.
One nice way to look at it is that you might not be able to use Mergesort on a massive database at nearly full capacity, while Heapsort will do fine.----------------- Hopefully PA is inconsistent.
@Puzzle Geek The top list of numbers were randomly generated. The bottom list of numbers is the top list sorted from smallest to biggest.----------------- Orange is my favorite number.