4 ms·
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 bub
by 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 agoThat'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 agoIt 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 agonot clrs