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...
When would you ever want bubblesort?
21–30 of 70 posts
Re: When would you ever want bubblesort?
#22When 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...
Also a good time to shelve any binary search because linear search will beat it for short sequences. The threshold varies by platform.
Re: When would you ever want bubblesort?
#23I've written a sort perhaps a handful of times in the last 40 years. Each of those was a bubble sort. I was nearly-always sorting These were rare cases where I didn't have a sort algorithm in a library -- perhaps because I needed to pass in a comparator that wasn't easily supported in the language. So I banged out whatever was easiest to get me moving on to the actual problem. If the sort became a noticeable part of…
> 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
Re: When would you ever want bubblesort?
#24Bubble sort is just fantastic to wind up arrogant algo-nerd snobs because you can bust it out for anything that is likely to be already sorted or nearly so and it dominates. Algo-nerd snobs rarely seem to take into account that knowledge and understanding of the input is the most crucial part. Do it in job interviews only if you've already decided you're unlikely to want to work there and be sure to be smiling and hu…
> it dominates
Not compared to insertion sort, which is the actual contender here.
Weirdly aggressive comment.
Re: When would you ever want bubblesort?
#25It's O(n) if the array is already sorted, which is better than other n*log(n) CS101 algorithms (merge/heap/quicksort)
That's my memory from college: bubble sort is fine when the data is almost completely sorted.
Re: When would you ever want bubblesort?
#26Can I have Cheeky Retorts for $100 Alex.
1. If you have a very large (say 100 million elements ) array in descending order, you can use Bubblesort to sort it in the ascending order - the worst case complexity is kn^2, and this is literaly the worst case, so its the equivalent of a sleep(t) routine for a large t ( depending on how sow your system is).
2. If you have a very small array (say n < 10), you can create toy examples where kn^2 < m*nlogn, for carefully chosen values of k, m & n. Say n = 3, k = 1, m = 7.
Re: When would you ever want bubblesort?
#27Earlier 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
No, I'm serious. With datasets that small, there's very little performance difference between the two methods, so a bubble sort isn't unreasonable at all. Depending on the circumstances, a bubble sort can be the better choice due to other considerations becoming relatively more important.
Re: When would you ever want bubblesort?
#28It's O(n) if the array is already sorted, which is better than other n*log(n) CS101 algorithms (merge/heap/quicksort)
Unless the element that should be at the start is at the end, everything else being sorted (ex: 2 3 4 5 6 1). Insertion sort is the best simple algorithm for almost sorted lists. In fact, it is generally considered the best O(n2) sorting algorithm.
Re: When would you ever want bubblesort?
#29> On some very particular hardwares bubblesort stills ends up better, like in this NVIDIA study, but you probably don't have that hardware.
The author might have misunderstood the hardware in question and the reasons why bubble sort works well here. You probably do have applicable hardware; it’s any GPU. The bubble sort wasn’t running on ray tracing hardware, it was just CUDA code. The reason bubble sort works well is because it’s running on a SIMD machine, and it’s better when all threads in a work unit (a “warp” in CUDA parlance) all do the same thing at all times.
If you try to do insertion sort on a SIMD machine, you’re very likely to approach worst-case O(N^2) performance very quickly, even when each individual thread involved would have had average-case perf on it’s own. Bubble sort is good for the parallel SIMD machine because of it’s deterministic and regular evaluation order that is the same across all threads.
Of course, it’s still true that for anything larger than very small arrays of data, bubble sort complexity is unacceptable on SIMD or parallel processors. There are better parallel sorting algorithms for that.
Re: When would you ever want bubblesort?
#30In 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 showed up at 5pm at his office, as he was bracing himself for the drive from Swarthmore back to Philly, wondering why he ever took this gig. I proposed a linear algorithm: Break 1..n into k bins, and only sort to detect collisions within each bin. Bins would have an average occupancy of 1, so it didn't matter what sort you used.
(I found this idea later in Knuth, and was briefly disillusioned that adults didn't read everything.)
I looked like George Harrison post-Beatles, I probably smelled of pot smoke, and he dismissed my idea. Then my dorm hall phone rang at 10pm, a professor of mine relaying an apology. For that and other ideas, the second edition of his book opened with thanks to me.
I'm surprised now that I realized then that bubble sort actually had the least overhead, in such an application. People don't use Strassen to multiple matrices unless the matrices are really big. For sorting, "really big" is 2 or 3 elements.