3 ms·
> there is never a good reason to use bubble sort Not true. Bubble sort is excellent for sorting very small arrays. See "Hoare’s Rebuttal and Bubble Sort’s Co
by dkbrk 3y ago
> there is never a good reason to use bubble sort
Not true. Bubble sort is excellent for sorting very small arrays.
See "Hoare’s Rebuttal and Bubble Sort’s Comeback (2020)" under "Fallback for sorting short arrays" and the performance results presented therein [0]. Discussion [1].
[0]: https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubble-sorts-comeback.html#fallback-for-sorting-short-arrays https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubb...
[1]: https://news.ycombinator.com/item?id=23363165 https://news.ycombinator.com/item?id=23363165
- kragen 3y agoremarkable, thank you all of the bubble sorts i tried compiling in this thread ended up being compiled to code with either conditional branches or (on arm thumb-2) a couple of conditionalized stores. but conditional stores don't require a pipeline flush, and it is of course perfectly correct that insertion sort depends on its inner loop having an unpredictable branch to get better performance on almost-sorted data, which bubble sort does not
- kragen 3y agoafter thinking about it some more, i was skeptical that this really implements bubble sort, but after trying it, it does python version of the inner loop max_ = arr[0] for j in range(1, i): y = arr[j] arr[j - 1] = min(max_, y) max_ = max(max_, y) arr[i - 1] = max_
- basementcat 3y agoIf you find yourself sorting small arrays, may I suggest a sorting network? https://en.m.wikipedia.org/wiki/Sorting_network https://en.m.wikipedia.org/wiki/Sorting_network