Thread: Fill in the blank code - generic Bubble sort - C

Originally Posted by laserlight

Wait, I just realised that you wrote: "According to Knuth (Vol 3) and Wikipedia the defining feature of insertion sort is that the terminating condition is when no swaps have occurred."

Yeah, that was a typo. Bubble sort terminates when no swaps have been made.

The implementation given by the OP is insertion sort according to Knuth (and the implementation is almost line for line exactly the same as Knuth provides for what he calls "straight insertion sort". I agree that these two sorts are very similar, but they iterate (and terminate) differently. Also, from Bubble sort - Wikipedia :

Bubble sort is asymptotically equivalent in running time to insertion sort in the worst case, but the two algorithms differ greatly in the number of swaps necessary. Experimental results such as those of Astrachan have also shown that insertion sort performs considerably better even on random lists. For these reasons many modern algorithm textbooks avoid using the bubble sort algorithm in favor of insertion sort.

So they're definitely different.

For reference, Knuth's bubble sort is attached.

I'm probably being overly pedantic, but since the two are quite different and presented as two distinct algorithms in all my reference books (I've seen insertion sort presented as bubble sort in intro to algorithm books, though) I prefer to also refer to them as distinct (which they are) and call them what the reference books call them.

Edit: It seems like they have a very similar discussion on Rosetta Code Talk:Sorting algorithms/Bubble sort - Rosetta Code

@HelpMeC sorry for going off on a tangent. If your teacher wants to call it bubble sort then fine :P But, well, it's insertion sort. Maybe these days the two algorithms are called bubble sort for convenience

Originally Posted by HelpMeC

Hodor -
The issue of the const is not completely clear to me... At first you have said that it's wrong to use there the const as we are swapping - and now you provide me with a new piece of code which defines more variables as constant.

So the const in this code regards only to the pointer elements themselves yes? We don't modify the pointers themselves anywhere...

Thank you!

What I really meant to say is that things should be consistent. I didn't mean that it was wrong to use const (it should be const) I meant that ignoring the const and discarding it the way the original program was doing is not good practice (you'll get a compiler warning that you're turning a const into a non-const and in this case it makes no difference, but in other cases it might and probably will). So either make them all non-const as I did in my first example (which I admit in hindsight was not the best approach), or better still make them all const as I did in my second improved example.

What compiler are you using? I think it's a good idea to turn warnings on and make sure the program compiles without warnings. Mixing const and non-const variables (like was happening in the swap part of the program) will emit a warning if you have warnings turned on (which you should). Also, those typedefs make things confusing, but I assume that maybe that was the idea, to try and make the quiz harder. But I doubt anyone would use those typedefs in real life code.

So the const in this code regards only to the pointer elements themselves yes? We don't modify the pointers themselves anywhere...

Yeah, that's right. Which is why the

Code:

Element temp = arrToSort[it+1];

part of the swap doesn't cause a problem (except the compiler warning) and you can't dereference it anyway because it's void*; it should be 'ConstElement temp' to be const correct and not get into bad habits

Edit: I guess the reason I'm babbling on about warnings is that when I was being taught C we'd get a zero if we handed in an assignment that had compiler warnings

Originally Posted by Hodor

For reference, Knuth's bubble sort is attached.

I'm more interested in "straight insertion sort". Canonical bubble sort is well known and quite clearly different from canonical insertion sort. The question here is whether this is an inefficient bubble sort or "straight insertion sort" (or both?)