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

  1. #16
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,490
    Quote Originally Posted by laserlight View Post
    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
    Attached Images Attached Images Fill in the blank code - generic Bubble sort - C-knuth_bubble-jpg 
    Last edited by Hodor; 2 Days Ago at 03:32 PM. Reason: I really must need sleep lol. Fixed sentence

  2. #17
    Registered User
    Join Date
    Nov 2019
    Posts
    70
    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!

  3. #18
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,490
    Quote Originally Posted by HelpMeC View Post
    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
    Last edited by Hodor; 2 Days Ago at 04:06 PM.

  4. #19
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,234
    Quote 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?)
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #20
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,490
    Quote Originally Posted by laserlight View Post
    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?)

    I think maybe it's kind of both now that I look at again. Some kind of weird hybrid Personally I think it's more like insertion sort, but *shrug*

  6. #21
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,490
    Ok, I'll agree. Let's just call it a terrible bubble sort.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with easy Array and bubble sort code
    By Dkman in forum C Programming
    Replies: 2
    Last Post: 01-03-2017, 08:32 AM
  2. Bubble Sort Code :(
    By irishfeeney92 in forum C Programming
    Replies: 22
    Last Post: 05-03-2011, 07:22 AM
  3. Bubble Sort Code Problem...
    By h4rrison.james in forum C Programming
    Replies: 7
    Last Post: 01-22-2009, 07:43 AM
  4. Problem with Bubble Sort code
    By lisa1234 in forum C++ Programming
    Replies: 7
    Last Post: 01-13-2004, 03:40 PM

Tags for this Thread