2 ms·

meh, an optimization, hardly "not working"

SomeoneFromCA 3y ago
It is not "an optimization", it is in the definition of Bubble Sort. What you have written is not a bubble sort, and therefore, by the fact of being not a bubble sort, is not a working bubble sort.
- thaumasiotes 3y ago
  That's not part of the definition of bubble sort. It's also not an improvement over the insertion sort. If you look at kragen's code, you'll see that running it on a list of e.g. 6 elements in ascending order will mean that you make 5 comparisons, swap 0 elements, and exit. (You do have to count from 1 to 6 as you do this.) The insertion sort is implemented as a bubble sort, interestingly enough, but one that doesn't consider the entire array at every iteration. Given that it's equally correct, it's not difficult to understand why it will always be faster than a bubble sort that does consider the entire array at every iteration.
  - SomeoneFromCA 3y ago
    It is in the definition in Wikipedia and most other sources I have checked. All the implementations I have seen so far, check if any swaps have happened, and stop if they have not.
    - kragen 3y ago
      not clrs
SomeoneFromCA 3y ago
In any case, you should retract you claim that Bubble Sort is slower on already sorted case. It is CS101, that bubble sort is one of the fastest in this case.
- kragen 3y ago
  after i posted the below comment to say 'oh yeah, you're right, thanks' someonefromca, perhaps inadvertently, edited the parent to say something completely different from what i was agreeing with. it previously said that there was a bug in the insertion sort code because it would swap things repeatedly, which is true and is a bug. my reply to their original comment is below oh yeah, you're right, thanks, it does do useless extra work if there are equal values in the list it should say if (tmp >= a[j-1]) break; however, this doesn't make it fail to terminate, which is a possible reading of your bug report

It is not "an optimization", it is in the definition of Bubble Sort. What you have written is not a bubble sort, and therefore, by the fact of being not a bubble sort, is not a working bubble sort.

thaumasiotes 3y ago
That's not part of the definition of bubble sort. It's also not an improvement over the insertion sort. If you look at kragen's code, you'll see that running it on a list of e.g. 6 elements in ascending order will mean that you make 5 comparisons, swap 0 elements, and exit. (You do have to count from 1 to 6 as you do this.) The insertion sort is implemented as a bubble sort, interestingly enough, but one that doesn't consider the entire array at every iteration. Given that it's equally correct, it's not difficult to understand why it will always be faster than a bubble sort that does consider the entire array at every iteration.
- SomeoneFromCA 3y ago
  It is in the definition in Wikipedia and most other sources I have checked. All the implementations I have seen so far, check if any swaps have happened, and stop if they have not.
  - kragen 3y ago
    not clrs

SomeoneFromCA 3y ago

In any case, you should retract you claim that Bubble Sort is slower on already sorted case. It is CS101, that bubble sort is one of the fastest in this case.

kragen 3y ago
after i posted the below comment to say 'oh yeah, you're right, thanks' someonefromca, perhaps inadvertently, edited the parent to say something completely different from what i was agreeing with. it previously said that there was a bug in the insertion sort code because it would swap things repeatedly, which is true and is a bug. my reply to their original comment is below oh yeah, you're right, thanks, it does do useless extra work if there are equal values in the list it should say if (tmp >= a[j-1]) break; however, this doesn't make it fail to terminate, which is a possible reading of your bug report