3 ms·
If you don't believe it, benchmark it. On very small arrays bubble sort is faster than quicksort as quicksort has a large constant overhead. Constant overhead
by bhaak 5y ago
If you don't believe it, benchmark it.
On very small arrays bubble sort is faster than quicksort as quicksort has a large constant overhead.
Constant overheads are usually disregarded in complexity analysis but in practice, it can be significant.
- deleted 5y ago[deleted]
- ogogmad 5y agoExcept I was comparing bubble sort to insertion sort. Read my comment again.
- bhaak 5y agoIf you compare bubble sort to insertion sort, bubble sort is preferable if you have a very small error (like swapping just one element).
- ogogmad 5y agoYou're wrong again. Insertion sort usually does less swaps than bubble sort. Question: Does it always do less swaps? Probably yes, I think.
- FabHK 5y agoPart of the article (and the whole article it references) are about how algorithm A that is guaranteed to perform fewer swaps than B is nevertheless slower in practice on modern machines because of other issues (predictability, data flow). > Most contemporary implementations of quicksort use Hoare partition, for obvious reasons: it does as many comparisons as the Lomuto partition and fewer swaps. > Given that Hoare partition clearly does less work than Lomuto partition, the question would be why ever teach or use the latter at all. […] implemented in a branch-free manner, Lomuto partition is a lot faster than Hoare partition on random data.