On Sat, 09 Feb 2008 23:07:44 +0100, Hrvoje Niksic wrote: > Steven D'Aprano <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
