The Bubble Sort 2467

Charlie Gibbs wrote On 10-25-05 13:35,:

Um, er, I was referring to something different: Not a procedure that keeps a table in order while building it but the algorithm referred to by Knuth as "straight insertion" (TAOCP algorithm 5.2.1S and variants). This algorithm starts with a (possibly) disordered array and produces a sorted array containing the same elements. C-ish pseudocode:

temp = arrayi; arrayj+1 = arrayj; else break; } arrayj+1 = temp; }

(Obviously, the implementation needn't look exactly like this. On some machines it may be faster to do all the data movement in one lump after discovering the proper insertion point, on some it may make sense to avoid the inner loop

Procedures that maintain order while building the data structure usually take more time than those that let the data pile up haphazardly and then sort the whole business at once. However, speed isn't the only concern: if the program actually needs data structure sorted at intermediate stages, it's probably better to keep it sorted as you go than to sort it repeatedly each time you need it. Also, even a procedure that takes more compute time overall may wind up taking less wall-clock time -- for example, you might be able to overlap new-item insertions with item-by-item I-O, doing more total work but doing it "in the shadow" of the I-O you were going to do anyhow.

But bubble sort? Pfui! Its initials characterize it well.

--