Bubble Sort: An archaeological algorithmic analysis (2003) [pdf](users.cs.duke.edu)
users.cs.duke.edu
Bubble Sort: An archaeological algorithmic analysis (2003) [pdf]
https://users.cs.duke.edu/~ola/papers/bubble.pdf
5 comments
Heh, I used bubblesort very much on purpose in one of my NES projects. You see, I have a list of up to 12 objects that I need to sort back-to-front, and I'm also on a 1.7 MHz processor. A fun property of bubblesort is that it is stable and in-place, so I can run the algorithm until it performs just one swap and then suspend it. Since objects don't move around that quickly and spawn/despawn events are infrequent, the sort eventually completes over the course of several frames, and the brief incorrect order is practically imperceptible during gameplay. The metric I was optimizing for was "least amount of CPU time spent on the sort during each frame" and, with that particular goal, bubblesort is the best choice by a landslide.
Insertion Sort is usually the quadratic sort used for small lists, is there a property of bubble sort that makes it better here?
Surprisingly yes, though it's a ridiculous edge case that you normally don't at all care about. Bubblesort can be managed with a single index, while selection sort requires two separate indices, and insertion sort requires shifting the list.
In 6502 assembly, you can do absolute addressing on the list, and you can very well set up your single pointer (an "index" register in this case) with overlapping array offsets, like so:
lda list, x ; load Nth element (4 cycles)
ldy list+1, x ; load N+1th element (4 cycles)
sta list+1, x ; swap into N+1th element (5 cycles)
tya ; 2 cycles (there is no STY abs, x)
sta list, x ; swap into Nth element (5 cycles)
This is about as fast as you can reasonably do the swap from an arbitrary point in the list, and it also means you only need to manage the X index as you scan through the list doing your comparisons. It results in just about the fastest possible single scan for the first swap. (You can also move the list into zeropage to ditch the TYA and save a few more cycles if you like, but I'm in the habit of avoiding zeropage expenditure unless absolutely necessary. It's really not here.)
Selection sort would be a very close second, and is worth consideration as it is algorithmically much more efficient (it'll complete the full in fewer overall frames) while the cost to shift the list for insertion sort makes it a distant third at best. But bubblesort wins for its simplicity and small code size. Of course this also assumes no code unrolling, which might bring selection sort up to performance par, at considerable ROM size, depending on the size of the list.
Note that my example is highly simplified for clarity. In reality the swap concerns a pair of parellel lists, one with the computed depth for the object, and a second for the metasprite index that is ultimately used for the draw order. The depth is recomputed every frame, which means the previous sort may be invalidated almost right away, which is why we restart the sort from the beginning every time. There's no point in trying to save our progress as we go.
In 6502 assembly, you can do absolute addressing on the list, and you can very well set up your single pointer (an "index" register in this case) with overlapping array offsets, like so:
lda list, x ; load Nth element (4 cycles)
ldy list+1, x ; load N+1th element (4 cycles)
sta list+1, x ; swap into N+1th element (5 cycles)
tya ; 2 cycles (there is no STY abs, x)
sta list, x ; swap into Nth element (5 cycles)
This is about as fast as you can reasonably do the swap from an arbitrary point in the list, and it also means you only need to manage the X index as you scan through the list doing your comparisons. It results in just about the fastest possible single scan for the first swap. (You can also move the list into zeropage to ditch the TYA and save a few more cycles if you like, but I'm in the habit of avoiding zeropage expenditure unless absolutely necessary. It's really not here.)
Selection sort would be a very close second, and is worth consideration as it is algorithmically much more efficient (it'll complete the full in fewer overall frames) while the cost to shift the list for insertion sort makes it a distant third at best. But bubblesort wins for its simplicity and small code size. Of course this also assumes no code unrolling, which might bring selection sort up to performance par, at considerable ROM size, depending on the size of the list.
Note that my example is highly simplified for clarity. In reality the swap concerns a pair of parellel lists, one with the computed depth for the object, and a second for the metasprite index that is ultimately used for the draw order. The depth is recomputed every frame, which means the previous sort may be invalidated almost right away, which is why we restart the sort from the beginning every time. There's no point in trying to save our progress as we go.
Related:
Bubble Sort: An Archaeological Algorithmic Analysis - https://news.ycombinator.com/item?id=19084059 - Feb 2019 (19 comments)
Bubble Sort: An Archaeological Algorithmic Analysis - https://news.ycombinator.com/item?id=15115769 - Aug 2017 (31 comments)
Bubble Sort: An Archaeological Algorithmic Analysis - https://news.ycombinator.com/item?id=19084059 - Feb 2019 (19 comments)
Bubble Sort: An Archaeological Algorithmic Analysis - https://news.ycombinator.com/item?id=15115769 - Aug 2017 (31 comments)
Even Obama isn't a big fan of bubble sort: https://www.righto.com/2012/11/obama-on-sorting-1m-integers-...
I do not understand why people act as if demonstrating bubble sort is going to forever taint minds and lead to disaster. When I was sitting in CS101 (or...probably data structures?), the professor was asking how you would sort an array. I "invented" bubble sort on the spot. Doubtless I was one of many who would have done the same.
Is it useful for any scenario? No, but you have to start somewhere, and might as well teach an algorithm that students are naively going to attempt on their own so you can note how terrible it is.
Is it useful for any scenario? No, but you have to start somewhere, and might as well teach an algorithm that students are naively going to attempt on their own so you can note how terrible it is.
No discussion of bubble sort is complete without mentioning that in casual conversation, the term "bubble sort" is used for any of the O(n²) variants that novice programmers might implement without guidance.