Bubblesort's big advantage is that it's the one sorting algorithm that I understand well enough to write from scratch in pinch.
When would you ever want bubblesort?
41–50 of 70 posts
Re: When would you ever want bubblesort?
#42Re: When would you ever want bubblesort?
#43I've done this. In a production application.
Why? It was the easiest sort I had memorized, I didn't have my college Data Structure 201 book handy. It did exactly what I wanted. And for my datasets, it was not impacting performance. Measurably? Probably. Noticeably from the user level? No. If it was slow, I would have changed it. I did it in BASIC.
But it was never my bottle neck. We're talking 10 or less items here most of the time, my bottleneck was sucking rows from the ISAM database on our 10 user, 16Mhz 68020.
I was doing best fit scheduling across a selection of resources.
It was a very cool system.
Re: When would you ever want bubblesort?
#44Why bubble sort when a slight modification can create a still simple but much more respectable algorithm called "comb sort".
Re: When would you ever want bubblesort?
#45In 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…
Yes, distinct elements. Fixed. That's the only way what I said makes sense, like how one error-corrects listening to a talk.
They were concerned with the case where n could be absurdly large, and wanted no time or space dependence on n. They improved my idea to cut the multiple of k needed for space.
Re: When would you ever want bubblesort?
#46In 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 a…
There's a fixed, rapidly vanishing probability distribution on bin occupancies, which evaluates to a constant per bin when one applies a sorting algorithm. One gets linear algorithms with different constants, depending on the sorting algorithm. You're thinking "deep end of the pool" worrying about b log b versus b^2. I was in the "shallow end of the pool" where the constants in front of fancy sorts took them out of the running.
Like I said about Strassen and matrix multiplication. Great algorithm, but it takes a while to kick in for the lead.
Re: When would you ever want bubblesort?
#47In 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…
Do people really use Strassen in practice? I don’t seem to see them in the wild.
Re: When would you ever want bubblesort?
#48Earlier 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
Especially if there’s little or no performance difference, may as well minimize code size.
Re: When would you ever want bubblesort?
#49Earlier quoted context omitted.
> 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 a…
There's a fixed, rapidly vanishing probability distribution on bin occupancies, which evaluates to a constant per bin when one applies a sorting algorithm. One gets linear algorithms with different constants, depending on the sorting algorithm. You're thinking "deep end of the pool" worrying about b log b versus b^2. I was in the "shallow end of the pool" where the constants in front of fancy sorts took them out of t…
> There's a fixed, rapidly vanishing probability distribution on bin occupancies,
Pretty much; my mistake was underestimating just how rapidly it vanishes. In actuality any sorting algorithm that isn't pathologically horrible garbage like bogosort will work fine, because it runs on meaningful numbers of elements so rarely that it doesn't matter (and I'm not totally sure bogosort is garbage enough).
> where the constants in front of fancy sorts took them out of the running.
For beating O(k log k), the constants don't actually matter, since they just increase the constant factor inside your O(k) runtime. It's just that apparently, the asymptotics don't matter much either for that.
Re: When would you ever want bubblesort?
#50Bubblesort is hard to beat if you're optimizing for object code size. I'm surprised that wasn't mentioned.
Unless you have a thousand of sorting routines it wouldn't matter much. And compilers generally produce a much larger code than actually possible, you can implement bubblesort in 16 bytes of x86-32 assembly [1] for example.