Anonymous user
Talk:Sorting algorithms/Bubble sort: Difference between revisions
Talk:Sorting algorithms/Bubble sort (view source)
Revision as of 19:38, 24 November 2008
, 15 years ago→This is bubble sort?: I agree with the old way
(→This is bubble sort?: I agree with the old way) |
|||
Line 19:
:That may be "your bubble short", but it is definitely not Bubble Sort. The basic feature of Bubble Sort is that it finishes sorting when there were no more swaps needed. Because of this, the best case execution time of Bubble Sort is O(N), i.e. linear time, which is significantly better than that of QuickSort, O(N*Log(N)). --[[User:PauliKL|PauliKL]] 18:51, 24 November 2008 (UTC)
::I also learned the bubble sort the way without checking for swaps (twice). I think we can all agree that the bubble sort is a comparison sort. If so, it would ONLY compare and swap items in the collection AND its best possible complexity would be O(n*log(n)). Adding this check for swaps seems like an optimization that takes it out of the comparison sort category, so I don't think it's part of the original algorithm. It may be the way that people implement it in practice (though I don't know why you'd use it in practice), and it may also be a welcome optimization (at least worth noting that it exists), but it doesn't seem like it's part of the idea of the sort. The "basic feature" of the bubble sort is the one it gets its name from: smaller elements bubbling to the top (front) of the collection. --[[User:Mwn3d|Mwn3d]] 19:38, 24 November 2008 (UTC)
| |||