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

langauges

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.