Anonymous user
Talk:Sorting algorithms/Bubble sort: Difference between revisions
Talk:Sorting algorithms/Bubble sort (view source)
Revision as of 16:22, 11 December 2008
, 15 years agoNew section: Never used?
(→This is bubble sort?: Optimized or un-optimized implementation.) |
(New section: Never used?) |
||
Line 81:
:::I don't know if it is necessary to have two implementations that has so little difference. In practice, the optimized version only requires decrementing the upper limit of the inner loop on each iteration and setting the initial value at the beginning. However, I notice both versions have been used in the implementations. So it might be good idea at least to mention on each implementation whether it uses optimized or un-optimized algorithm. --[[User:PauliKL|PauliKL]] 15:42, 11 December 2008 (UTC)
== Never used? ==
In the algorithm description, there is sentence ''"Because of its abysmal O(n2) performance, it is never used anywhere else"''.
That is, of course, totally untrue. Since bubble sort is the simplest sorting algorithm, it is the best choice for situations where speed is not critical (e.g. when sorting only small datasets), and/or when code size is important. In addition, it is stable and requires no additional space for temporary storage.
Further, there is nothing abysmal about O(n<sup>2</sup>) performance. Many commonly used algorithms have the same performance (e.g. insertion sort, selection sort). Worst case performance of Bubble Sort is the same as that of the best implementations of QuickSort, i.e. O(n<sup>2</sup>), and much better than naive implementation of QuickSort (infinite time). And best case performance for Bubble sort is much better than that of QuickSort.
Of course, Insertion Sort is only slightly more complex than Bubble Sort, and it is somewhat faster, so it could be preferred.
--[[User:PauliKL|PauliKL]] 16:22, 11 December 2008 (UTC)
| |||