When would you ever want bubblesort? • Hacker News Board

Re: When would you ever want bubblesort?

#31

Post by dehugger » Wed, Dec 06, 2023, 1:48 AM UTC

jcalvinowens wrote: post #12

NobodyNada wrote: post #10

Earlier quoted context omitted.

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…

I explained another way to interpret what OP said. Your way is boring and uninteresting: this is a forum for discussion, so I picked the more interesting way :)

Picked a more belligerent interpretation, certainly. Your original comment made no allowances for the obvious interpretation and said that the consequences of the simple solution were "apocalyptically bad". While I found the ensuing discussion interesting you definitely did not approach it from a standpoint of engendering more interesting conversation. You could have gotten the same result much more easily by simply pointing out that this was not thread safe and only works in a single threaded application, and instead of nit picking we could have actually talked about better options for concurrency.

Re: When would you ever want bubblesort?

#32

Post by hakuseki » Wed, Dec 06, 2023, 1:57 AM UTC

Syzygies wrote: post #30

In college in the 1970's, I took a combinatorial algorithms class with Herb Wilf. He explained that choosing a subset of k distinct elements from 1..n uniformly at random was likely k log k, because you needed to detect collisions, and "sorting" k elements was k log k. (Always check your assumptions. Sorting has an k log k lower bound if all you can do is compare elements. With integers 1..n, one can do much more.) I…

I guess you mean k log k, not n log n.

Re: When would you ever want bubblesort?

#33

Post by svachalek » Wed, Dec 06, 2023, 1:58 AM UTC

jbandela1 wrote: post #20

For an N^2 sorting algorithm, I think insertion sort is superior to bubble sort when you want something simple: http://warp.povusers.org/grrr/bubblesort_misconceptions.html

That link seems to insist on defining bubble sort without a termination condition, which is not how I think of bubble sort and I suspect is not how anyone is defining it in the cases it argues against. Also the use case in this article isn't listed.

Re: When would you ever want bubblesort?

#34

Post by Syzygies » Wed, Dec 06, 2023, 2:03 AM UTC

hakuseki wrote: post #32

Syzygies wrote: post #30

In college in the 1970's, I took a combinatorial algorithms class with Herb Wilf. He explained that choosing a subset of k distinct elements from 1..n uniformly at random was likely k log k, because you needed to detect collisions, and "sorting" k elements was k log k. (Always check your assumptions. Sorting has an k log k lower bound if all you can do is compare elements. With integers 1..n, one can do much more.) I…

I guess you mean k log k, not n log n.

yep, thanks. "n log n" is how one always says it, it becomes a local variable in its phrase. Oops.

Re: When would you ever want bubblesort?

#35

Post by dekhn » Wed, Dec 06, 2023, 2:05 AM UTC

jcalvinowens wrote: post #8

pengaru wrote: post #7

Earlier quoted context omitted.

> > so it adds almost nothing to the CPU time. > If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad. I'm assuming that's not what you meant? I think it's apparent they didn't mean the CAS atomic instruction, just the compare-and-swap operation in bubblesort. Nothing in their comment suggested this was a multi-threaded situation.

>> 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" in this case is the innermost functionality of bubblesort.

I assume the author is https://github.com/aappleby but I don't see any obvious candidate for this code. Maybe this? https://github.com/aappleby/metroboy but I can't see why a gate-level emulator woudl need to render transparent items using painter's algorithm.

Re: When would you ever want bubblesort?

#36

Post by glitchc » Wed, Dec 06, 2023, 2:06 AM UTC

Bubble-sort is great if you have many cores to spare but no extra memory. It parallelizes nicely and works in-place.

Insertion sort is great if you don't have any cores or memory to spare. It uses one core and works in-place.

Selection sort is much like insertion sort, runs in-place, single-threaded, but it will be faster if your CPU is much faster than your memory access as it uses more comparisons and fewer swaps.

Re: When would you ever want bubblesort?

#37

Post by dekhn » Wed, Dec 06, 2023, 2:06 AM UTC

vandyswa wrote: post #21

When the bucket of things to sort drifts below count ~100, bubble sort will hammer it into order in an amount of time which is, for all intents and purposes, zero. Use the smallest hammer which drives the nail...

This is also known as "hardware caches and branch prediction beat smart humans almost every time"

Re: When would you ever want bubblesort?

#38

Post by a1369209993 » Wed, Dec 06, 2023, 2:25 AM UTC

Syzygies wrote: post #30

In college in the 1970's, I took a combinatorial algorithms class with Herb Wilf. He explained that choosing a subset of k distinct elements from 1..n uniformly at random was likely k log k, because you needed to detect collisions, and "sorting" k elements was k log k. (Always check your assumptions. Sorting has an k log k lower bound if all you can do is compare elements. With integers 1..n, one can do much more.) I…

> Bins would have an average occupancy of 1, so it didn't matter what sort you used.

That's not quite right, though - you only care about the average occupancy if your sorting algorithm is O(b) for b elements. If you're using a O(b^2) sort, you actually care about the root-mean-square occupancy (or in general just the average runtime, or just the total runtime since you'll multiply the average by the number of bins anyway).

The k-bin approach is definitely much faster than O(k log k), but I'm fairly sure it's slightly slower than truely linear, asymptotically, since the runtime will be something like 1+0+4+1 in typical cases, where linear would have to be 1+0+2+1.

Edit: on some cursory Monte Carlo testing, the sum of squares of occupancies actually seems to still converge on a constant factor (of two) times the sum of plain/linear occupancies, which I was not expecting but does make the above point rather moot. (Also, the sum of cubed occupancies seems to converge on a factor of five, which seems downright bizzare.)

(Tangential edit: The factors seem to be 1 2 5 15 52±2 200±20, which might be https://oeis.org/A000110, though none of the interpretations there seem obviously related.)

Re: When would you ever want bubblesort?

#39

Post by amluto » Wed, Dec 06, 2023, 2:31 AM UTC

Syzygies wrote: post #30

In college in the 1970's, I took a combinatorial algorithms class with Herb Wilf. He explained that choosing a subset of k distinct elements from 1..n uniformly at random was likely k log k, because you needed to detect collisions, and "sorting" k elements was k log k. (Always check your assumptions. Sorting has an k log k lower bound if all you can do is compare elements. With integers 1..n, one can do much more.) I…

> choosing k elements from 1..n uniformly at random

Can you clarify the problem?

k elements uniformly at random, independently, with replacement, sounds like it’s trivially O(k), or perhaps O(k log n) if n is so big that you need O(k log n) bits to merely represent the answer. (Those logs are pesky and can appear and disappear in different models of computation!)

Maybe you mean k distinct elements? Off the top of my head, if n is not huge (n = O(k), or more concretely, n 1, and I would probably start with 2 if I were implementing this), I would make an array of all the elements and draw k of them using any of a number of straightforward algorithms. (Fischer-Yates, for example, but I admit I had to look up the name.)

For larger n, make a hash table to store the elements selected so far. Now repeat k times: choose an element at random and retry if it’s a duplicate. Then add it to the hash table and continue. Each iteration takes at most 1/c tries on average, so the overall expected time is O(k). (For n Thinking of this as sorting seems odd, but I admit I’m thinking about this in 2023, not the 1970s :)

Re: When would you ever want bubblesort?

#40

Post by doubloon » Wed, Dec 06, 2023, 2:52 AM UTC

Because in a certain company i couldnt use anything except a limited old language and there was no straightforward way to sort a list of custom types and internet searching was limited . You cannot just download your favorite open source library or whatever in a lot of environments, you are stuck with the tools you got.