Could someone explain what the utility of bubble sort is? I've read that even in cases where an O(nlogn) sort is impractical, insertion or selection sort is preferred.
Bubble sort is good for sorting particles in a particle system. Particles need to be drawn from the furthest from the camera to the closest to the camera.
Each frame the particles move a little bit, and the camera moves a little bit.
That means that in a given frame most, if not all, of the particles are probably already sorted. In addition, if the sort order has changed, it's probably only requires swaps of adjacent particles.
Because of this, bubble sort is often best sort to use for this operation.
Wouldn't insertion sort be even better then? As far as I recall insertion sort is always better than bubble sort, easier to understand too so I do not see why bubble sort is so popular in CS courses.
you have a small (3-5) fixed size array that you need to sort with very simple code.
A classic case is to enforce a defined lock ordering when you have more than two locks in dynamic objects that you all need to acquire. In this case open coded bubble sort is good and beats calling a complicated library function.
The other case is your objects are known to be nearly already sorted. In this case bubble sort is a very good algorithm too (although it may be better to avoid a full sort then)
In short bubble sort is often a good choice when anything else would be over engineered.
To expand on this point: simplicity ("just do what you need") is often under valued.
One simple data structure trick I learned recently (from Knuth) is: people often use complicated balanced tree libraries like b or rb. You only need a balanced tree library when the sort keys are in-balanced. One simple trick is to hash the input keys. As long as your hash function is good enough, the keys will be already spread out and you can then use a much simpler non balanced tree.
Insertion sort is almost always faster than bubble sort and just as easy to implement, so no there is no reason to implement bubble sort that I know of.
If you already have a list of objects, then bubble sort can beat insertion sort in terms of space, because it doesn't have to construct a second list. That's pretty much the only place left where bubble sort has any advantage, but when you need it, nothing else will do.
Insertion sort does swap elements in place so requires zero additional memory. It is like bubble sort but with better good cases and is as easy to implement. I recommend reading the Wikipedia article about it.
Comments
Could someone explain what the utility of bubble sort is? I've read that even in cases where an O(nlogn) sort is impractical, insertion or selection sort is preferred.
Bubble sort is good for sorting particles in a particle system. Particles need to be drawn from the furthest from the camera to the closest to the camera.
Each frame the particles move a little bit, and the camera moves a little bit.
That means that in a given frame most, if not all, of the particles are probably already sorted. In addition, if the sort order has changed, it's probably only requires swaps of adjacent particles.
Because of this, bubble sort is often best sort to use for this operation.
Wouldn't insertion sort be even better then? As far as I recall insertion sort is always better than bubble sort, easier to understand too so I do not see why bubble sort is so popular in CS courses.
bubble sort is useful for two cases:
you have a small (3-5) fixed size array that you need to sort with very simple code.
A classic case is to enforce a defined lock ordering when you have more than two locks in dynamic objects that you all need to acquire. In this case open coded bubble sort is good and beats calling a complicated library function.
The other case is your objects are known to be nearly already sorted. In this case bubble sort is a very good algorithm too (although it may be better to avoid a full sort then)
In short bubble sort is often a good choice when anything else would be over engineered.
To expand on this point: simplicity ("just do what you need") is often under valued.
One simple data structure trick I learned recently (from Knuth) is: people often use complicated balanced tree libraries like b or rb. You only need a balanced tree library when the sort keys are in-balanced. One simple trick is to hash the input keys. As long as your hash function is good enough, the keys will be already spread out and you can then use a much simpler non balanced tree.
Insertion sort is almost always faster than bubble sort and just as easy to implement, so no there is no reason to implement bubble sort that I know of.
If you already have a list of objects, then bubble sort can beat insertion sort in terms of space, because it doesn't have to construct a second list. That's pretty much the only place left where bubble sort has any advantage, but when you need it, nothing else will do.
Insertion sort does swap elements in place so requires zero additional memory. It is like bubble sort but with better good cases and is as easy to implement. I recommend reading the Wikipedia article about it.
http://en.wikipedia.org/wiki/Insertion_sort
It swaps elements in place in the list it builds, but it requires building another list. Bubble sort doesn't.