sort functions in python
jeff at schwabcenter.com
Sat Feb 9 04:09:06 CET 2008
Steven D'Aprano wrote:
> On Fri, 08 Feb 2008 17:00:27 -0800, t3chn0n3rd wrote:
>> Do you think it is relatively easy to write sort algorithms such as the
>> common Bubble sort in Python as compared to other high level programming
> You realise that bubble sort is one of the worst possible sort algorithms
> possible, particularly on modern hardware? It's not the worst: bogo sort
> and bozo sort are worse, but bubble sort is still pretty atrocious.
That's the conventional wisdom, mostly because CS professors need a "bad
algorithm" to show undergrads, but it's not really accurate. The truth
is that bubble-sort's performance depends strongly on the input data.
In the worst case, yes, bubble-sort is O(n^2); however, for
almost-sorted data (only a few elements out of place), bubble-sort is
actually one of the fastest known algorithms. For already-sorted data,
bubble-sort is O(n). If you expect your data to be pretty nearly sorted
already, but you just want to make sure (e.g. because a small number of
elements may have been inserted or removed since the last sort),
bubble-sort is a good choice.
More information about the Python-list