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. -- http://mail.python.org/mailman/listinfo/python-list
