Don wrote: > dsimcha wrote: >> == Quote from Don ([email protected])'s article >>> "the bubble sort seems to have nothing to recommend it, except a catchy >>> name " - Knuth. >> >> Well, the bubble sort distance is a pretty good metric of how similarly >> ordered >> two lists are. It's useful, for example, in statistics such as Kendall's >> Tau. One of the easiest ways to calculate it is...with a bubble sort. > > I don't think that's a coincidence. It seems to be defined in terms of > bubble sort! > > The whole bubble sort phenonemon seems to be self-perpetuating. There > were loads of really crap algorithms in the 1950's. Why was this one not > forgotten with the rest?
Because it's SIMPLE. And because for the small sample sizes used in most classes (still?) scaling with n^2 isn't all that bad. Someone said that the insertion sort is better even for small sample sizes, but if you don't have an array type that implements insertion, then that means writing an extra loop to move things down. I might have suggested that the exchange sort was a good choice. But with small sample sizes and limited memory (no longer a significant problem for cases where this is even vaguely reasonable) the bubble sort isn't that bad. In fact it's difficult to measure the difference as n tends towards 3. For n == 2 there's no other even vaguely reasonable choice. The problem with bubble sorts is the factor of n^2. My teacher might well have been wrong when he put n as high as 25 for where the bubble sort was optimal, but it's clearly optimal when n is less than 4. It's just that those cases don't matter in the real world. (And actually, they'd probably be handled with a case statement, or a nested if.) But if you have code that needs to handle sorting array sizes between 3 and 25 (varying in the calls, and tending towards the low end), then there's no reason to go for anything more complicated. Of course, a better choice yet is often to use a library function. Even if the low end calls have excess overhead, it won't matter much, and you don't need to worry about coding errors. (Yeah, I believe that Knuth said there was no reason for the bubble sort existing. And without knowing the exact context in which he said it, I'm not going to call him wrong. The times to use it are not only extremely limited, there's also a tendency to use it at the wrong times, just because you have the code handy, and it's easy.) P.S.: If you have an Array class, and the array class has an insert method, then the insertion sort is clearly better for building a sorted list. It's less clear if you're sorting a list that you already have, and you're trying to avoid allocating new memory. Especially if it's not stored a container class with an insert method. N.B.: If the bubble sort weren't taught, it would be continually re- invented. And as it's so rarely the proper choice, it needs to be warned against. Preferably by having someone write something that, sorts things interactively, and then having them start adding things to be sorted. But processors may be fast enough to defeat this experiential learning unless you add things in a way that doubles the collection size each time you make an addition.
