Question

http://ideone.com/oIbYk

So I've managed to implement all the CS101 basic \(O(n^2)\) comparison sort algorithms in C (minus shell sort, but that \(O(nlog^2n))\))

1. I have two bubblesorts in there; one is an implementation of the pseudocode on the wikipedia article for bubblesort, and the one before that is something I came up with. Are there any differences between the two (i.e. number of read/write/comparison/swaps)?

2. Below selection_sort, I've got a macro for testing each sorting algorithm, but right above that is a commented out function that does the exact same procedure. Should I us

Answer 1

2. cont: Should I use the macro for such things, or should I always try to wrap such procedures into functions whenever possible?

3. Is there any better way to implement a generic swap() function than the way I did it?

4. Is there any way to improve the shuffling algorithm (comprising randrange and shuffle()) ?

5. Any ways to improve my code, in general?

Answer 2

Oh and one final question related to the algorithms: Why is both bubble_sort and my_bubble_sort much, much slower than insertion_sort and selection_sort?

Answer 3

Here's a slightly better version: http://ideone.com/GWlcJ

Answer 4

I will try to answer the questions one at a time. For the bubblesort question: there are two problems with it, one is the hidden constant factor that makes bubble slower than the other O(n^2) sorts, and the fact that, even if the input will be completely randomized, a bad input for bubblesort can happen easily, one with large numbers at the beginning of the array (namely, the "turtles", if my memory does not fail me). Do it by hand, or change your program to see it. If you have an array like 9, 7, 8, 6, 3, 2, 1, 4, 5 bubble sort will have to make several swaps.

Answer 5

Another thing: rand() function is not that good in most systems. Not that you should be concerned in this case, since it's not industrial code, but I think one can approximate it to somewhat of a Poisson distribution, and, worst than that, there are a lot of gotchas regarding it. Take a peek http://www.azillionmonkeys.com/qed/random.html here. You might find something useful :-)

Answer 6

yeah, on a reversed array it will have to do sum(range(1, 11)) swaps

Answer 7

In that case, how do I improve my randrange and shuffle functions?

Answer 8

There are a couple of ideas in the link I posted. I use an idea that I saw somewhere in StackOverflow to break the range into disjoint sets, so one outcome does not influence any other.
http://stackoverflow.com/questions/2509679/how-to-generate-a-random-number-from-within-a-range-c Ryan Reich's post.

Answer 9

My code looks like this now: http://ideone.com/xYXNZ