61–70 of 70 posts
Bubblesort is hard to beat if you're optimizing for object code size. I'm surprised that wasn't mentioned.
Earlier quoted context omitted.
> I was nearly-always sorting In my opinion, a bubble sort is a solid choice for that sort of use case.
Are you being cheeky? Cause I would think insertion sort would be a more than reasonable alternative
I would pick a standard library sort function at that point.
Why bubble sort when a slight modification can create a still simple but much more respectable algorithm called "comb sort". https://www.delftstack.com/tutorial/algorithm/comb-sort/
In practical terms using integers, this makes almost no difference *except* it can be performed using faster shift and add operations:
gap = ((gap > 2;
For even more speed, I'd also recommend in-lining this to eliminate the function call. Properly implemented, respectable speed can be achieved from a really trivial implementation.
Before I knew anything about sorting algorithms, I invented my own algorithm to sort the high score list in my little BASIC game. It was very simple: Find the highest score, swap it to the top and continue, this time starting with the second item, until done. I imagine that if I ever find myself in need of writing a sorting algorithm from memory, I'll still go with this one.
Earlier quoted context omitted.
>> You do the compare-and-swap when you're iterating over the objects to do some other render pass OP is describing using CAS to bubblesort an array while it is concurrently read by another thread rendering something based on its contents? That seems kind of wild to me but I don't know why else you add the words "some other". Sometimes sorting is an optimization and isn't necessary for correctness. The idea of two th…
You misunderstood. The CAS term isn't related to threads in aappleby's comment. aappleby is saying the following: He wrote a game engine, it renders transparent items using the painter's algorithm, which requires the items to be sorted in Z. He has a routine that iterates over all items to render them, and bubble-sorts the items in-place while iterating over the items (all in the same thread). The "compare and swap"…
Earlier quoted context omitted.
>> You do the compare-and-swap when you're iterating over the objects to do some other render pass OP is describing using CAS to bubblesort an array while it is concurrently read by another thread rendering something based on its contents? That seems kind of wild to me but I don't know why else you add the words "some other". Sometimes sorting is an optimization and isn't necessary for correctness. The idea of two th…
No, there was no mention of concurrency. As I understsand it, OP was describing a "render pass" that looked like this: for (int i = 0; i And adding a "compare and swap" to the loop: one step of a bubble sort, to keep the objects "mostly sorted": for (int i = 0; i obj[i+1]) swap(&obj[i], &obj[i+1]) // do some rendering or something } Thus, "do[ing] the compare-and-swap when you're iterating over the objects to do some…
Bubblesort is hard to beat if you're optimizing for object code size. I'm surprised that wasn't mentioned.
Array v with N elements:
First pass: go from v[0] to v[N-1] comparing v[i] with v[i+i] Second pass: go from v[N-1] to v[0] comparing v[i] with v[i+i]
This is so obvious that it should have a name...
Bubblesort is hard to beat if you're optimizing for object code size. I'm surprised that wasn't mentioned.
Yes. Ignorant question: if you use bubble sort but go through the array in alternating senses, could it not improve locality and speed? Array v with N elements: First pass: go from v[0] to v[N-1] comparing v[i] with v[i+i] Second pass: go from v[N-1] to v[0] comparing v[i] with v[i+i] This is so obvious that it should have a name...