News for hackers. Stuff that matters.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by yoz-y on Monday August 28, 2017 @11:24AM (#15117149)
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.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by jdmichal on Monday August 28, 2017 @12:24PM (#15117750)
I 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.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by s-phi-nl on Monday August 28, 2017 @12:41PM (#15117939)
Anecdotally, 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.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by thethirdone on Monday August 28, 2017 @01:05PM (#15118168)
I 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.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by Retric on Monday August 28, 2017 @01:50PM (#15118598)
A-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.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by vanderZwan on Monday August 28, 2017 @04:16PM (#15119708)
That's more or less radix sort, no?
Re:Bubble Sort: An Archaeological Algorithmic Analysis by Retric on Monday August 28, 2017 @04:18PM (#15119718)
Yep, though radix and bucket sorts are closely related.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by mannykannot on Monday August 28, 2017 @11:57AM (#15117469)
I 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.

Re:Bubble Sort: An Archaeological Algorithmic Analysis by jdmichal on Monday August 28, 2017 @12:14PM (#15117625)
Bubble 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?

Re:Bubble Sort: An Archaeological Algorithmic Analysis by s-phi-nl on Monday August 28, 2017 @01:19PM (#15118289)
Do you know of any source that compares the coefficients for bubble sort, insertion sort, and selection sort? This sounds interesting.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by jdmichal on Monday August 28, 2017 @03:13PM (#15119220)
Given that those are all average case n² algorithms, the article's figure is probably a good representation:

https://users.cs.duke.edu/~ola/bubble/bubble.html#fig:quadso...

Mannykannot is correct that the full coefficient is dependent on the machine and exact code. However, we can make some refinements based on the algorithms alone.

Bubble sort is n² / 2, as it processes one less element per pass. This is a pretty common pattern, so it's good to remember.

Insertion sort starts at zero elements and processes one extra element per pass. So it's also n² / 2. However, on average each pass only needs to process half the elements in order to find the correct insertion point. So it's actually n² / 4. If you use a binary search, it becomes n log n -- n passes, each perform a log n binary search. (This is usually called binary insertion sort.)

However, those numbers are in comparisons, which is typically what sort algorithms are measured by. It assumes that all memory operations are constant time. But you might also want to keep track of swaps or other memory movement. For instance, when you add the memory swaps back to the binary insertion sort, it's O(n²) again, because it still has to perform an average of n / 2 swaps on every pass -- O(n * (log n + n / 2)) = O(n²).

Choice of data structure can also make an impact. Insertion sort is not awesome on memory arrays, because it has to perform a block copy for every insert. However, on linked lists, that single-element shift happens for "free" when you perform the insert.

Re:Bubble Sort: An Archaeological Algorithmic Analysis by mannykannot on Monday August 28, 2017 @02:49PM (#15119041)
I 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.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by krylon on Monday August 28, 2017 @01:46PM (#15118559)
I remember how clever I felt when I discovered binary search, and how humiliated I was when I discovered that not only had I not been the first person to come up with it, but that it was so obvious pretty much everyone had "discovered" it independently. ;-)
Re:Bubble Sort: An Archaeological Algorithmic Analysis by jdmichal on Monday August 28, 2017 @02:51PM (#15119051)
I "rediscovered" tries in order to cheat at scrabble my freshman year. So it goes!

https://en.wikipedia.org/wiki/Trie

Re:Bubble Sort: An Archaeological Algorithmic Analysis by abecedarius on Monday August 28, 2017 @12:38PM (#15117906)
I'd expect insertion or selection sort to be easiest to invent; I remember coming up with selection sort as a kid. Where bubble sort comes out on top is being the simplest to code (if you have for-loops) -- not quite the same thing.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by yoz-y on Monday August 28, 2017 @12:06PM (#15117553)
I 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.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by krylon on Monday August 28, 2017 @12:57PM (#15118097)
Paradoxically, 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.

Re:Bubble Sort: An Archaeological Algorithmic Analysis by lederhosen on Monday August 28, 2017 @02:18PM (#15118829)
qsort(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.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by krylon on Tuesday August 29, 2017 @11:47AM (#15125074)
I 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. ;-)

Re:Bubble Sort: An Archaeological Algorithmic Analysis by throwaway613834 on Monday August 28, 2017 @02:07PM (#15118732)
Intuitive? 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.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by edflsafoiewq on Monday August 28, 2017 @03:13PM (#15119223)
It'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.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by daveFNbuck on Monday August 28, 2017 @11:32AM (#15117202)
Do 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.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by yoz-y on Monday August 28, 2017 @11:41AM (#15117300)
Yes. I thought that "scales" was the same thing as balances when used for a single object. I see that it does not.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by jamessb on Monday August 28, 2017 @01:07PM (#15118189)
A "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.
Re:Bubble Sort: An Archaeological Algorithmic Analysis by daveFNbuck on Monday August 28, 2017 @12:07PM (#15117568)
Why is bubble sort what you would use for heavy bags?
Re:Bubble Sort: An Archaeological Algorithmic Analysis by yoz-y on Monday August 28, 2017 @12:45PM (#15117980)
The 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.