sort functions in python

[Steven D'Aprano]

On Sat, 09 Feb 2008 23:07:44 +0100, Hrvoje Niksic wrote:

> Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> writes:
> 
>> 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.
> 
> I've never seen anything better than bubble sort being called bubble
> sort.

What, you didn't read the post you're replying to? There goes your 
credibility, right out the window and accelerating fast. The very next 
paragraph in my post said:

"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:"

So as you can see, there are at least two quite different sort 
algorithms, with very different speeds and behaviours, and both are 
called bubble sort by the people who put them on the web.

The Wikibooks version always makes the same number of passes over the 
list, regardless of it's initial order. Even if the list is sorted, it
still walks over the list O(N**2) times, doing pointless comparisons over 
and over again. It ends up doing a constant 1/2*N*(N-1) comparisons, 
regardless of the state of the list, whether it is sorted, reversed or 
something in between.

http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Bubble_sort

The Planet Math version does not run a fixed number of times. If the list 
is already sorted, it only walks it once, doing only (N-1) comparisons. 
But if the list is far from sorted, it can end up doing N*(N-1) 
comparisons.

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

If we're going to call them both bubble sort, we might as well call 
virtually any exchange sort (e.g. gnome sort, comb sort, cocktail sort, 
insertion sort, etc.) "bubble sort". And that would be stupid.

Sure, they're all *similar* algorithms, with O(N**2) behaviour, but their 
differences are significant: they differ in their best, worst and average 
behaviour and the coefficient multiplier.

> Comb sort is definitely regarded as a different algorithm, 

And so it should be.

> and cocktail sort is no better than bubble sort anyway.

Not according to Wikipedia:

http://en.wikipedia.org/wiki/Cocktail_sort


 
>> It's rather like any divide-and-conquer sorting algorithm being called
>> quicksort.
> 
> Where have you seen this?  I've never heard of non-quicksort
> divide-and-conquer algorithms (such as mergesort) being referred to as
> quicksort.


My apologies for not being more clear. What I meant was that lumping all 
exchange-sorts (a family of algorithms) as "bubble sort" (a specific 
example of the family) is as bogus as lumping all divide-and-conquer 
algorithms together as "quicksort" would be, if anyone did it.



-- 
Steven