Beginner Exercises

[xander333]

For example: I have a full sentence, and somewhere in my cout<<, I use the array. Can it order the sentences with the arrays?

[S6k9GNh0]

http://codepad.org/4yE6ArR8

EDIT: Improved: http://codepad.org/5I9ITvR8

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.

[chrisname]

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.

[Albatross]

I take it nobody here is going to try to implement smoothsort.

-Albatross

[chrisname]

Isn't that one supposed to be ridiculously complicated?

[Albatross]

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.

-Albatross

[chrisname]

Oh, it's Dijkstra. He's mentioned a lot in a book I have.

[S6k9GNh0]

Final draft: http://codepad.org/flvR8oE9

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.

EDIT2: And sleep... I'll try tomorrow...

[jwC5fSEw]

Would this be a proper bubble sort? Or did I overcomplicate it? (I just did it in Notepad to see how it worked)

1 4 9 10 5 8 13
1 4 9 5 10 8 13
1 4 5 9 8 10 13
1 4 5 8 9 10 13

[chrisname]

I've never seen a bubblesort that started from the middle of the array, but yeah, that's the idea.

[helios]

It didn't start from the middle. It just so happens that the first half was mostly sorted.

[chrisname]

Oh yeah. Hey, it was 5:43am.

[S6k9GNh0]

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.

[jwC5fSEw]

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.

[S6k9GNh0]

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...

http://userweb.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/EWD797.html

[jwC5fSEw]

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.

[S6k9GNh0]

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.

[MottMan]

Here is how I did Pancake Glutton: http://codepad.org/sGA1udX5

It's probably not very ideal but it's just the way I did it...

[firedraco]

Instead of using ++ and -- like you are, why don't you just do something like:

cout << "How many Pancakes did person " << i+1 << " eat?\n";

[MottMan]

I don't know...thanks for pointing that out :S

EDIT: Thanks a lot for this post as it is helped and entertained a lot :) I particularly enjoyed

Strings are your friends, until they betray you.