A: For small arrays. I would add: particularly if you need a stable sort algorithm, which is either complex (Block Sort) or uses O(n) space (Merge Sort).
The only use I've seen is incrementally sorting large arrays during brute-force search of said arrays, since that is approximately free and brute-force search is pretty efficient and fast on modern CPUs. Set a "sorted" flag if/when the array is eventually sorted.
The idea was that the vast majority of arrays in a large set are not searched often enough to justify the cost of sorting them and sorting is an expensive operation if you are computing on a deadline. You also don't always know which ones will be heavily searched ahead of time. Using bubblesort, only the heavily accessed arrays end up sorted but as a side-effect of search rather than having separate heuristics to decide when/what to sort.
I used bubblesort on purpose in a game project. Specifically, to sort sprites in an NES game back to front, lazily, spending as few CPU cycles as possible. Bubblesort on the very small list (a dozen objects max), and early exit after the first swap. It eventually completes, and that was just fine. It's tiny, incredibly simple, and somewhat resilient to the list changing from frame to frame as objects spawn and despawn. Each partial sort makes some progress no matter what.
A few other algorithms would have fit the bill just as well, but bubblesort is perfectly adequate, so that's what will likely ship. More complex algorithms end up losing out due to greater initial overhead or larger ROM size.
I've used bubblesort when simulating LEO satellite constellations, calculating which satellite is closest to a location. I used one single backwards pass of bubblesort, so O(n) every k timesteps to bring the closest to the head of the array, then every timestep just do one backwards bubblesort pass over the first few in the array. Given satellites move smoothly, if you initialize right (a few full passes at the start to get the closest few at the front) and get the constants right so a satellite outside the front few in the array can't have moved far enough to become closest without being promoted to the front few by a periodic full pass, then you always maintain the closest at the front of the array very cheaply. And this has the advantage of also being very simple to code.
If you need a stable sort, can't be bothered finding a massive oversize library to link to, and only need to sort a relatively small number of objects on a system that's resource-constrained, I'm guessing?
For small sets, or small-ish sets when you are coding quick, don't have a convenient standard library sort to hand, and are prioritising correctness over absolute performance.
Though in reality almost never: you almost always have a convenient built-in sort that is as quick & easy to use (likely quicker & easier), and in circumstances where the set is small enough for bubblesort to be just fine, the speed, memory use, or other properties of what-ever other sort your standard library uses aren't going to be a problem either.
As others have pointed out, sometimes it is useful for partial sorts due to the “always no less sorted than before at any point in the process (assuming no changes due to external influence)” property.
wrt:
> If you make each frame of the animation one pass of bubblesort, the particles will all move smoothly into the right positions. I couldn't find any examples in the wild,
There are hundreds of sort demos out there, both live running and on publicly hosted videos, that show the final positions by hue, getting this effect. Seems odd that they couldn't find a single one.
EDIT: actually, I can't find any of the rainbow based sort demos I was thinking of, a lot of promising links seem dead. I take back my little moan!
bubble sort is sometimes used in information retrieval use cases for reranking top k based on some signals, especially specific to a user profile. I feel heap sort comes up as well, yet neither are necessarily the most efficient.
Yeah, the article beat me to the gamedev example. Bubble sort being able to always "soft sort" on every iteration makes it the easiest to suspend and resume when you have a lot of other work to do, and when sorting is low priority.
Also, general wisdom to be mindful of data sizes and cache coherency. O(NLogN) vs. O(N^2) doesn't mean much when you're only sorting a few dozen items. Meanwhile, O(N) space can have drastic performance hitches when reallocating memory.
The article, and many of the responses, are hinting at the fact that bubblesort is an example of an anytime algorithm. This is a wide class of algorithms which provide a correct answer after some amount of time, but provide an increasingly good answer in increasing amounts of time short of the completion time. This is a super valuable property for real time systems (and many of the comments about games and animations discuss that). The paper that introduced me to the category is "Anytime Dynamic A*" [0], and I think it's both a good paper and a good algorithm to know.
On 8-bit and 32-bit microcontrollers (e.g. 8-bit AVR, 32-bit ESP8266/ESP32), Insertion sort is 6X faster than Bubble Sort on random data. I have tested this up to about N=1000.
Both Insertion sort and Bubble sort are O(N^2). Both are stable sorts. Insertion sort consumes only about 10-20 bytes more flash memory than Bubble sort. It's hard to think of situations where Bubble sort would be preferred over Insertion sort.
Shell sort is vastly superior if you can afford an extra 40-100 bytes of flash memory. (It's not too much more complicated than Insertion sort, but sometimes, we don't have 100 extra bytes.) It is O(N^k), where k ≈ 1.3 to 1.5. As soon as N ⪆ 30, Shell sort will start clobbering Insertion sort. For N ≈ 1000, Shell sort is 10X faster than Insertion sort, which in turn is 6X faster than Bubble sort. Unfortunately Shell sort is not stable.
Comb sort has a similar O(N^k) runtime complexity as Shell sort. But it seems slower than Shell sort by a constant factor. Comb sort is also not stable. I cannot think of any reason to use Comb sort over Shell sort.
Quick sort is not much faster than Shell until about N ≈ 300. Above that, the O(N*log(N) of Quick sort wins over the O(N^k) of Shell sort. But Quick sort is not stable.
Merge sort is stable and runs in O(N*log(N)), but it consumes an extra O(N) of RAM, which may be impossible on a microcontroller. You may be forced back to Insertion sort for a stable sort.
In all your big-O analyses, remember: n = 3 more often than you think. n = 12 a lot more often than you think. If that's your case, there's nothing wrong with bubble sort unless you have very tight performance constraints.
Worse, big-O always hides a constant factor. What's bubblesort's constant? What's quicksort's? It wouldn't surprise me if, for small enough n (2 or 3, and maybe a bit higher), bubblesort is actually faster.
Note well: I have not actually benchmarked this.
Also note well: Determine what your n is; don't assume that it's either large or small.
When sorting eigenpairs of a dense matrix, usually tou end up with a Schur decomposition. The basic operation that you can do is swap two adjacent eigenvalues on the diagonal, so bubblesort is a natural candidate.
32 comments
[ 4.6 ms ] story [ 45.3 ms ] threadThe idea was that the vast majority of arrays in a large set are not searched often enough to justify the cost of sorting them and sorting is an expensive operation if you are computing on a deadline. You also don't always know which ones will be heavily searched ahead of time. Using bubblesort, only the heavily accessed arrays end up sorted but as a side-effect of search rather than having separate heuristics to decide when/what to sort.
A few other algorithms would have fit the bill just as well, but bubblesort is perfectly adequate, so that's what will likely ship. More complex algorithms end up losing out due to greater initial overhead or larger ROM size.
Though in reality almost never: you almost always have a convenient built-in sort that is as quick & easy to use (likely quicker & easier), and in circumstances where the set is small enough for bubblesort to be just fine, the speed, memory use, or other properties of what-ever other sort your standard library uses aren't going to be a problem either.
As others have pointed out, sometimes it is useful for partial sorts due to the “always no less sorted than before at any point in the process (assuming no changes due to external influence)” property.
wrt:
> If you make each frame of the animation one pass of bubblesort, the particles will all move smoothly into the right positions. I couldn't find any examples in the wild,
There are hundreds of sort demos out there, both live running and on publicly hosted videos, that show the final positions by hue, getting this effect. Seems odd that they couldn't find a single one.
EDIT: actually, I can't find any of the rainbow based sort demos I was thinking of, a lot of promising links seem dead. I take back my little moan!
Also, general wisdom to be mindful of data sizes and cache coherency. O(NLogN) vs. O(N^2) doesn't mean much when you're only sorting a few dozen items. Meanwhile, O(N) space can have drastic performance hitches when reallocating memory.
[0] https://cdn.aaai.org/ICAPS/2005/ICAPS05-027.pdf
Both Insertion sort and Bubble sort are O(N^2). Both are stable sorts. Insertion sort consumes only about 10-20 bytes more flash memory than Bubble sort. It's hard to think of situations where Bubble sort would be preferred over Insertion sort.
Shell sort is vastly superior if you can afford an extra 40-100 bytes of flash memory. (It's not too much more complicated than Insertion sort, but sometimes, we don't have 100 extra bytes.) It is O(N^k), where k ≈ 1.3 to 1.5. As soon as N ⪆ 30, Shell sort will start clobbering Insertion sort. For N ≈ 1000, Shell sort is 10X faster than Insertion sort, which in turn is 6X faster than Bubble sort. Unfortunately Shell sort is not stable.
Comb sort has a similar O(N^k) runtime complexity as Shell sort. But it seems slower than Shell sort by a constant factor. Comb sort is also not stable. I cannot think of any reason to use Comb sort over Shell sort.
Quick sort is not much faster than Shell until about N ≈ 300. Above that, the O(N*log(N) of Quick sort wins over the O(N^k) of Shell sort. But Quick sort is not stable.
Merge sort is stable and runs in O(N*log(N)), but it consumes an extra O(N) of RAM, which may be impossible on a microcontroller. You may be forced back to Insertion sort for a stable sort.
And while I've never hit a case I would think it would have merit with data known to be pretty close to properly sorted.
Worse, big-O always hides a constant factor. What's bubblesort's constant? What's quicksort's? It wouldn't surprise me if, for small enough n (2 or 3, and maybe a bit higher), bubblesort is actually faster.
Note well: I have not actually benchmarked this.
Also note well: Determine what your n is; don't assume that it's either large or small.