This holds a working implementation of the the insertion sort. I'm still working on figuring out how to bind the amounts to the position in the array.
For instance, I can sort an array no problem, but the sort replaces itself in a sense so even if the first were to have 1000000000 and the highest, it will become player 10 because that's where the sort put it. Even if I make a temp array of it, I have no decent way of having the positions finding the correct corresponding value so it wouldn't help me. I'm actually a bit stuck, however the sort does work...
EDIT: Added a paired structure for use in an array. However, there are problems with this still.
I wrote some implementations of a few sorts (I didn't get to heapsort, mergesort or quicksort, which were the last 3 in my list) but I did bubble, selection and IIRC I also did insertion. I didn't test them yet, but I'll go find them.
Yes, but it's insanely fast (worst case performance: O(nlogn), best case performance: O(n), worst complexity total: O(n), worst complexity auxiliary O(1)), relative to other comparison sorts.
This one sorts amount, which is binded to a position, correctly. Try it out :D
I can try other sorts... Give me a bit though. The last one made my head hurt TxT Nearly had to break out the scratch paper.
EDIT: OMFG.... Smoothsort will most definitely require scratch paper.
So the bubble algorithm just iterates through the numbers, swapping according until none need to be swapped? That is pretty simple but I can see why it would be slow.
Yep. It can also be slightly optimized to keep track of the highest number that was swapped, so it won't try to swap any of the numbers after that number. This cuts down on the iterations.
Out of honesty, I'm having a rather rough time understanding most of smooth sort. Not because I don't understand how it works, its that I don't understand how the things that make it works work so I don't know how to implement it from scratch. It is interesting though and I will probably be making an article on algorithms after this for fun :D
EDIT: Like for instance, why is Leonardo's numbers significant when it comes to heap size? That makes no sense to me but I'm not exactly sure the point of Leonardo's numbers in the first place...
I'd appreciate such an article. Looking through this topic has gotten me interested in sorting algorithms, so I'm implementing some as a challenge. Bubble sort was easy. However, I couldn't even get my mind around implementing insertion sort without looking at some source code. This stuff fascinates me, however. I need to find a good algorithm book.
It's a matter of understanding what the algorithm is actually doing. WIth that, I can implement anything I want from scratch. I find this healthier than looking at source code and copying since I tend to take more than enough and fail to learn as much.