4 ms·
From the article: "Just as a quicksort algorithm that sorts in O(n log n) comparisons is fundamentally better (except in very small sets) than a bubble sort tha
by Fargren 16y ago
From the article:
"Just as a quicksort algorithm that sorts in O(n log n) comparisons is fundamentally better (except in very small sets) than a bubble sort that typically takes O(n^2) comparisons."
Small nitpick: while average time of the quicksort algorithm is O(n log n), the worst case is O(n^2).
- Jach 16y agoAnother nitpick, several good quicksorts use insertion sorts for small sets which absolutely trounce the bubble sort. (I really think the bubble sort should never be mentioned; it's unintuitive and slow as tar. Teach the insertion sort!)
- burgerbrain 16y agoBubble sort is the fastest sort for sets of size two. Now, arguably there isn't really much functional difference between sorts on sets of size two, but the simplicity of bubble sort gives it an advantage for this extreme case.
- lukeschlather 16y agoThat generally applies to anywhere you're coding in something raw like C or assembly on very small datasets and don't want to deal with the mental overhead of picking and writing an efficient sorting algorithm. For sets of less than 100 items, it's not worth the bother. I actually did that in a programming contest once, having solved the hard part of the problem and being left with nothing but sorting the results.