The Bubble Sort 2468

Patrick Scheible

If you just sort the keys, and leave the rest of the record in place, then you sort a fixed length item of key + pointer to rest of record, and the adjacency argument doesn't apply. Plus you spend less time moving data around.

This bubble sort business keeps coming up. I really don't know why. If you are interested in sorting in memory, as opposed to external sorting on disk, then here are two clbuttes of sorts, those that take O(N^2) (insertion, selection and bubble sorts) and those that take O(NlogN) in the average case. If the amount of data you have is small, it really doesn't matter which method you use (within reason), but if you have a lot of data, then you should obviously choose an O(NlogN) method. Then, which particular algorithm you choose depends on your goal. Quicksort gives the best average time, but performs like O(N^2) in the worst case, while heapsort is slightly slower on average, but always O(NlogN). So you choose depending on what you want to guarantee.

--brian

-- "What's life? Life's easy. A quirk of matter. Nature's way of keeping meat fresh."