sort functions in python
Steven D'Aprano
steve at REMOVE-THIS-cybersource.com.au
Sun Feb 10 02:42:53 CET 2008
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
More information about the Python-list
mailing list