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.
[ Parent
| on HN ]
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?