News for hackers. Stuff that matters.
Re:Bubblesort, rocksort, and cocktail-shaker sort by taneq on Wednesday December 16, 2020 @07:08AM (#25441632)
It's good when there are a lot of elements off by a short distance in a mostly sorted list. The go-to use case that I've seen is depth sorting for 3D rendering on really low end hardware. Polygons usually don't move much in the Z-order each frame, so you run a few passes of bubblesort per frame for a good-enough linear-time sort.
Re:Bubblesort, rocksort, and cocktail-shaker sort by NortySpock on Wednesday December 16, 2020 @09:25AM (#25442807)
Also, two passes of cocktail-shaker sort (back and forth bubble sort) would guarantee that the top and bottom z-order would be correct, which would probably be good enough to keep really obviously bad z-ordering at bay.

Like you say, when it's already partially sorted and you're just having to maintain a slowly-updated list, a single partial-sort pass per frame could be quite enough to maintain a good-enough ordering of a list.

Re:Bubblesort, rocksort, and cocktail-shaker sort by ogogmad on Wednesday December 16, 2020 @07:23AM (#25441723)
Do you know how it compares to insertion sort, which is also fast on nearly sorted lists?
Re:Bubblesort, rocksort, and cocktail-shaker sort by taneq on Wednesday December 16, 2020 @07:33AM (#25441795)
Nope, sorry - never saw them compared head to head like that. I'd imagine they'd be pretty similar though.
Re:Bubblesort, rocksort, and cocktail-shaker sort by ogogmad on Wednesday December 16, 2020 @07:39AM (#25441840)
Without further information, I would be strongly tempted to swap out the bubble sort for insertion sort. Less code and should be faster.