6 ms·

Bubble Sort: An Archaeological Algorithmic Analysis

47 points by mac01021 9y ago

flashdance 9y ago
"Well, I think the bubble sort would be the wrong way to go." --Barack Obama
- yoz-y 9y ago
  I did not know about this and Googled the line out of curiosity. TIL
  - rkuykendall-com 9y ago
    Same, googled and found this great story: http://fortune.com/2015/08/18/mindware-nisbett/ http://fortune.com/2015/08/18/mindware-nisbett/ > Shortly after Barack Obama announced he was running for president in the fall of 2007, Google’s CEO, Eric Schmidt, interviewed him in front of a large audience of Google employees. As a joke, Schmidt’s first question was, “What is the most efficient way to sort a million 32- bit integers?” Before Schmidt could ask a real question, Obama interrupted: “Well, I think the bubble sort would be the wrong way to go,” a response that was in fact correct. Schmidt slapped his forehead in astonishment, and the room broke out in applause. Later, in the question-and-answer period, Obama assured his audience, “I am a big believer in reason and facts and evidence and science and feedback,” and promised that he would run the government accordingly. > In the audience that day was a product manager named Dan Siroker, who made a decision on the spot to go to work for Obama. “He had me at bubble sort.”
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 ago
  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.
  - yoz-y 9y ago
    Yes. I thought that "scales" was the same thing as balances when used for a single object. I see that it does not.
    - daveFNbuck 9y ago
      Why is bubble sort what you would use for heavy bags?
      - yoz-y 9y ago
        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.
    - jamessb 9y ago
      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.
- mannykannot 9y ago
  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.
jjuhl 9y ago
The only situation where I've actually employed bubble sort in production code was in a situation where the container to be sorted was guaranteed to be at most 5 elements (and usually 3) and was usually already sorted - and calling this sort was done a lot. All other sorts proved to have too much startup overhead or too much code that bloated caches.. so yes, I wrote a bubble sort to be used there and it performed quite well. But I would generally never recommend bubble sort for 99.9% of cases - but just once in a blue moon it actually can be the right answer.
juancn 9y ago
I re-discovered bubble sort when I was 12, with a deck of cards and a C64. It wasn't until I got to college that I learned it had a name. I believe it's a very intuitive algorithm, it has likely been rediscovered many times.

47 points by mac01021 9y ago

flashdance 9y ago

"Well, I think the bubble sort would be the wrong way to go." --Barack Obama

yoz-y 9y ago
I did not know about this and Googled the line out of curiosity. TIL
- rkuykendall-com 9y ago
  Same, googled and found this great story: http://fortune.com/2015/08/18/mindware-nisbett/ http://fortune.com/2015/08/18/mindware-nisbett/ > Shortly after Barack Obama announced he was running for president in the fall of 2007, Google’s CEO, Eric Schmidt, interviewed him in front of a large audience of Google employees. As a joke, Schmidt’s first question was, “What is the most efficient way to sort a million 32- bit integers?” Before Schmidt could ask a real question, Obama interrupted: “Well, I think the bubble sort would be the wrong way to go,” a response that was in fact correct. Schmidt slapped his forehead in astonishment, and the room broke out in applause. Later, in the question-and-answer period, Obama assured his audience, “I am a big believer in reason and facts and evidence and science and feedback,” and promised that he would run the government accordingly. > In the audience that day was a product manager named Dan Siroker, who made a decision on the spot to go to work for Obama. “He had me at bubble sort.”

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 ago
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.
- yoz-y 9y ago
  Yes. I thought that "scales" was the same thing as balances when used for a single object. I see that it does not.
  - daveFNbuck 9y ago
    Why is bubble sort what you would use for heavy bags?
    - yoz-y 9y ago
      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.
  - jamessb 9y ago
    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.
mannykannot 9y ago
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.

jjuhl 9y ago

The only situation where I've actually employed bubble sort in production code was in a situation where the container to be sorted was guaranteed to be at most 5 elements (and usually 3) and was usually already sorted - and calling this sort was done a lot. All other sorts proved to have too much startup overhead or too much code that bloated caches.. so yes, I wrote a bubble sort to be used there and it performed quite well. But I would generally never recommend bubble sort for 99.9% of cases - but just once in a blue moon it actually can be the right answer.

juancn 9y ago

I re-discovered bubble sort when I was 12, with a deck of cards and a C64. It wasn't until I got to college that I learned it had a name. I believe it's a very intuitive algorithm, it has likely been rediscovered many times.