[HN Gopher] Bubble Sort: An archaeological algorithmic analysis ...
___________________________________________________________________
Bubble Sort: An archaeological algorithmic analysis (2003) [pdf]
Author : aragonite
Score : 35 points
Date : 2024-07-19 03:06 UTC (5 days ago)
(HTM) web link (users.cs.duke.edu)
(TXT) w3m dump (users.cs.duke.edu)
| dang wrote:
| 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)
| zeta0134 wrote:
| 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.
| cwmma wrote:
| Insertion Sort is usually the quadratic sort used for small
| lists, is there a property of bubble sort that makes it better
| here?
| zeta0134 wrote:
| 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.
| petercooper wrote:
| Even Obama isn't a big fan of bubble sort:
| https://www.righto.com/2012/11/obama-on-sorting-1m-integers-...
___________________________________________________________________
(page generated 2024-07-24 23:04 UTC)