sort functions in python

[Steven D'Aprano]

On Fri, 08 Feb 2008 19:09:06 -0800, Jeff Schwab wrote:

> 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.

It depends on what you mean by "bubble sort". There are many different 
variations of bubble sort, that are sometimes described by names such as 
comb sort, cocktail sort, exchange sort, and sometimes merely referred to 
bubble sort. It's rather like any divide-and-conquer sorting algorithm 
being called quicksort.

I'm as guilty of that as anyone else -- the example code I posted, raided 
from Wikibooks is very different from this bubble sort algorithm from 
PlanetMath:

http://planetmath.org/encyclopedia/Bubblesort.html

def bubblesort(L):
    done = False
    while not done:
        done = True
        for i in xrange(len(L)-1):
            if L[i+1] <= L[i]:
                L[i], L[i+1] = L[i+1], L[i]
                done = False
    return L

This one runs significantly faster than the earlier one I posted.

Another vital factor is, what language are you implementing the sort 
routine in? The conventional wisdom for low-level languages like assembly 
and C doesn't necessarily hold for high-level languages like Python. 
Comparisons are slow in Python and fast in C; in C a good algorithm will 
minimize the amount of moves, while in Python a good algorithm will 
minimize the number of comparisons.

Finally, what hardware are you running on? There are interactions between 
hardware caches and pipes that can ruin the performance of an otherwise 
promising algorithm.


But all those factors aside, I fear that your attempt to rehabilitate the 
reputation of bubble sort is misplaced. Here's another person who wants 
to defend bubble sort:

"A fair number of algorithm purists (which means they've probably never 
written software for a living) claim that the bubble sort should never be 
used for any reason. Realistically, there isn't a noticeable performance 
difference between the various sorts for 100 items or less, and the 
simplicity of the bubble sort makes it attractive."

http://linux.wku.edu/~lamonml/algor/sort/bubble.html

But then on the same person's page on insertion sort:

"The insertion sort is a good middle-of-the-road choice for sorting lists 
of a few thousand items or less. The algorithm is significantly simpler 
than the shell sort, with only a small trade-off in efficiency. At the 
same time, the insertion sort is over twice as fast as the bubble sort 
and almost 40% faster than the selection sort."

http://linux.wku.edu/~lamonml/algor/sort/insertion.html

He gives sample C code for both, and the bubble sort has eight lines of 
code, versus nine for insertion sort (excluding bare braces).

Perhaps what he should have said is:

"Bubble sort is a tiny bit simpler than insertion sort, and almost twice 
as slow!"



-- 
Steven