19 ms·

Insertion Sort is usually the quadratic sort used for small lists, is there a property of bubble sort that makes it better here?

by cwmma 2y ago

zeta0134 2y ago
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.

Insertion Sort is usually the quadratic sort used for small lists, is there a property of bubble sort that makes it better here?

by cwmma 2y ago

Insertion Sort is usually the quadratic sort used for small lists, is there a property of bubble sort that makes it better here?

zeta0134 2y ago

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.