3 ms·
Paradoxically, bubblesort can actually be pretty fast on small inputs (i.e. short arrays). I once experienced this first hand in C codebase. I had to sort an a
by krylon 9y ago
Paradoxically, bubblesort can actually be pretty fast on small inputs (i.e. short arrays).
I once experienced this first hand in C codebase. I had to sort an array of structs where the array never contained more than ~50 members, and the comparison was very simple; in that case, bubblesort actually ran faster than the qsort(3) supplied by the compiler.
Then again, at such small scale, the performance win is so tiny it usually is not worth the effort.
- lederhosen 9y agoqsort(3) is quite slow because it can not inline the compare function. If you created a 'generic' bubble sort that take a compare function pointer and no LTO optimization (or use an inlined c++ sort), the quick sort algorithm might be faster even on 50 elements.
- krylon 9y agoI had suspected that might be a factor. Either way, at 50 elements, if the difference in performance between qsort and bubblesort has significant impact on overall performance, there is probably something very wrong. ;-)