6 ms·
For me it seems that bubble sort is mostly popular because it is very intuitive. It is the typical way of how would one sort a bunch of heavy bags with only sca
by yoz-y 9y ago
For me it seems that bubble sort is mostly popular because it is very intuitive. It is the typical way of how would one sort a bunch of heavy bags with only scales, which is another question that comes up often.
- daveFNbuck 9y agoDo you mean with only balances? With scales you would just weigh each bag once and sort the weights. In either case, why would bubble sort be preferred? I'd think you would want to minimize how many times you have to move the bags on and off the scale/balance.
- yoz-y 9y agoYes. I thought that "scales" was the same thing as balances when used for a single object. I see that it does not.
- daveFNbuck 9y agoWhy is bubble sort what you would use for heavy bags?
- yoz-y 9y agoThe problem goes something like this: You have N number of bags of the same size but different (maybe) weights. You have nothing to write and only balances. The easiest way to sort them is to put them in a row, compare them two by to and swap them in order.
- jamessb 9y agoA "Pair of scales" does mean the same as a "balance", but "scales" on its own sually means a device containing an electronic (or spring) weighing mechanism.
- mannykannot 9y agoI suspect that if you took students who knew just enough programming to write a sort, but with no prior exposure to sorting algorithms, and asked them to write a sort, many would come up with a bubble sort (I think that was true of me.) If so, then it is worth mentioning simply to point out its inefficiency. Also, the bubble sort serves a useful pedagogical purpose for introducing the concept of time complexity analysis, especially if my guess is correct, as then it does not look like a contrived example. After all, the goal of computing education is not just to churn out mechanical algorithm-implementors, and it is hard to teach good design without something to compare it to.
- yoz-y 9y agoI remember that when I have started to code and had no internet or books, just examples of other code, and needed to sort something. I have written a bubble sort too. But back then being slow was sometimes a feature, as I knew nothing about threads or clocks, so the processor ticks commanded the speed of my shitty game.
- jdmichal 9y agoBubble sort is still the only sort I will write by hand. It's fast to write and easy to read. It's in-place and stable. It has a stupidly low coefficient in front of that n² that keeps it in the running until about 100 elements. Once I get beyond that, I select a pre-written sort that's tailored to my needs. Do I need stability? Do I need in-place? Do I need a local copy at all, or can I stream the results?
- s-phi-nl 9y agoDo you know of any source that compares the coefficients for bubble sort, insertion sort, and selection sort? This sounds interesting.
- mannykannot 9y agoI think you will find it to be data-, implementation-, language-, and platform-dependent. You could consider implementing versions of each in a compiled language and look at the disassembled machine- or byte-code generated for them. If your target processor is pipelined and/or does branch prediction, speculative execution, caching or virtual memory, these could all affect the relative performance on a given input.
- jdmichal 9y agoI would think that some form of insertion sort is the most intuitive. That's what people use when they do things like sort cards in their hand.
- s-phi-nl 9y agoAnecdotally, the professor of my algorithms class had us all sort cards manually and asked us to describe the algorithm we used when we began studying sorting algorithms. Most of us used either selection sort or insertion sort.
- thethirdone 9y agoI would think bucket sort (into the suits) would be the most common. Whenever I am sorting named papers I always do it with 26 piles.
- Retric 9y agoA-K in 13 piles then suits in 4 piles is a little faster. Or if your space limited you can group A-7 then 8-K.
- vanderZwan 9y agoThat's more or less radix sort, no?
- Retric 9y agoYep, though radix and bucket sorts are closely related.
- krylon 9y agoParadoxically, bubblesort can actually be pretty fast on small inputs (i.e. short arrays). I once experienced this first hand in C codebase. I had to sort an array of structs where the array never contained more than ~50 members, and the comparison was very simple; in that case, bubblesort actually ran faster than the qsort(3) supplied by the compiler. Then again, at such small scale, the performance win is so tiny it usually is not worth the effort.
- lederhosen 9y agoqsort(3) is quite slow because it can not inline the compare function. If you created a 'generic' bubble sort that take a compare function pointer and no LTO optimization (or use an inlined c++ sort), the quick sort algorithm might be faster even on 50 elements.
- krylon 9y agoI had suspected that might be a factor. Either way, at 50 elements, if the difference in performance between qsort and bubblesort has significant impact on overall performance, there is probably something very wrong. ;-)
- throwaway613834 9y agoIntuitive? Bubble sort is the most counterintuitive sort I know after Shell sort. I still have to think hard about what it does every time I read it and I'm not sure if I remember it accurately to be honest. So I don't understand how people find it intuitive. Insertion sort is far, far more natural.
- deleted 9y ago[deleted]
- edflsafoiewq 9y agoIt's not even particularly clear that bubble sort halts. Unlike insertion sort, the loop variant is not trivial to write down. I suppose the best thing about it is that it is very clear that if it halts, the array is sorted.