5 ms·

Oh my, I’m that guy today. Whoever said it, I have a super hard time believing DHH couldn’t implement bubble sort on a whiteboard. Am I the only one? I get th

Oh my, I’m that guy today. Whoever said it, I have a super hard time believing DHH couldn’t implement bubble sort on a whiteboard. Am I the only one? I get that people hate whiteboard/algorithm interviews, but bubble sort? for i = 0..n: for j = i..n: if arr[i] > arr[j]: arr[j], arr[i] = arr[i], arr[j] Everyone in this field should be able to do this, maybe not right away, maybe not without bugs, but with help within 45 minutes.

LandR 7y ago
Yeah, this is barely a step above fizzbuzz. If you can't do that without help in 45 minutes, what can you actually do? I think the actual problem is most developers / programmers are just bad at the job, and then go in a huff when this is pointed out.
jcranmer 7y ago
Off the top of my head, I could write selection sort, insertion sort, merge sort, quick sort, and with a few minutes of thinking about it, even heapsort. But bubble sort? It's a useless sort, even worse than selection and insertion sort, which have their advantages in certain circumstances. So I don't bother to remember what the algorithm for bubble sort is in the first place.
- seba_dos1 7y ago
  Do you learn algorithms by blindly memorizing their steps? There's nothing to remember in bubble sort, if you know that it "bubbles" by swaping the elements you're already done.
  - dragontamer 7y ago
    The main "issue" I have is that if you write a "bubble" sort backwards, then its suddenly insertion sort instead and much more efficient. For people who know about knots out there... its like asking for somebody to tie a Granny Knot instead of a square-knot. Anyone who actually practiced knot-tying will "accidentally" tie a square-knot instead (because the square-knot is stronger for the same level of effort). Similarly, bubble sort is the "bad" way to write insertion sort. Anybody who actually practiced writing sorts will write insertion sort by accident instead.
    - seba_dos1 7y ago
      I'm pretty sure the original meaning of "I can't even write bubble sort on a whiteboard" wasn't "I would accidentally write a more efficient algorithm instead" ;)
  - jcranmer 7y ago
    I learn algorithms by memorizing their general structure and filling in gaps using the invariants of the process. A selection sort is pulling the largest elements to the end of the list; an insertion sort sorts the first N elements and inserts the next element; a quick sort picks a pivot to divide the list for sorting; mergesort sorts half the list and then merges them; heap sort heapifies the input (this takes me some time to remember how to do efficiently) and then pulls out the top repeatedly. But bubblesort? There's no invariant. Sure, I can tell you that it's this structure: for i = ? .. ?: for j = ? .. ?: i1, i2 = ?, ? if A[i1] < A[i2]: A[i1], A[i2] = A[i2], A[i1] But, with the lack of invariants, I don't know how to fill in the ? correctly. With trial and error, I could write a correct sort from this template. But insertion sort and selection sort also follow this template (as does any other sorting network if you try hard enough), and I can't guarantee that I'd hit bubblesort instead of those.
    - seba_dos1 7y ago
      I don't buy it. Bubble sort is the simplest, the most naive one, you don't even have to remember anything about it. do sorted = true for i = 0 .. n-1: if A[i] > A[i+1]: A[i], A[i+1] = A[i+1], A[i] sorted = false while not sorted That's already a perfectly valid bubble sort. You can then optimize it by noticing that after nth iterations nth elements will already be sorted, and you're done. If you're trying to recall this algorithm from memory by comparing it with other sorting algorithms you've memorized, you're probably doing it wrong, because there's hardly a place for real world usage of bubble sort, so your memory of it is naturally going to fade away. The trick is - you don't even need to memorize it or recall any structure to fit it into. Just imagine an inefficiently bubbling array of numbers in your head and that's it.
eesmith 7y ago
Now I get to be that guy. Your i only needs to go to n-1, and your j can start with i+1. More importantly, what you wrote is a selection sort, not a bubble sort! A bubble sort swaps neighboring terms. Eg, if I interpret the code in 2.1 of https://users.cs.duke.edu/~ola/bubble/bubble.html https://users.cs.duke.edu/~ola/bubble/bubble.html correctly, the 'definitive' version is: for i = n-1..0: for j = 0..i: if arr[j+1] < arr[j]: arr[j], arr[i] = arr[i], arr[j]
- dickeytk 7y ago
  Fair point. Perhaps it is harder than I thought without looking anything up or testing? At least to get the canonical version written down.
  - eesmith 7y ago
    I think it's that "bubble sort" has come to mean "a simple O(N²) sort implementation", of which there are many. But the selection sort just feels more natural than the actual bubble sort. At the very least, selection sort doesn't get my face to scrunch up in a scowl at all those memory movements.

LandR 7y ago

Yeah, this is barely a step above fizzbuzz. If you can't do that without help in 45 minutes, what can you actually do? I think the actual problem is most developers / programmers are just bad at the job, and then go in a huff when this is pointed out.

jcranmer 7y ago

Off the top of my head, I could write selection sort, insertion sort, merge sort, quick sort, and with a few minutes of thinking about it, even heapsort. But bubble sort? It's a useless sort, even worse than selection and insertion sort, which have their advantages in certain circumstances. So I don't bother to remember what the algorithm for bubble sort is in the first place.

seba_dos1 7y ago
Do you learn algorithms by blindly memorizing their steps? There's nothing to remember in bubble sort, if you know that it "bubbles" by swaping the elements you're already done.
- dragontamer 7y ago
  The main "issue" I have is that if you write a "bubble" sort backwards, then its suddenly insertion sort instead and much more efficient. For people who know about knots out there... its like asking for somebody to tie a Granny Knot instead of a square-knot. Anyone who actually practiced knot-tying will "accidentally" tie a square-knot instead (because the square-knot is stronger for the same level of effort). Similarly, bubble sort is the "bad" way to write insertion sort. Anybody who actually practiced writing sorts will write insertion sort by accident instead.
  - seba_dos1 7y ago
    I'm pretty sure the original meaning of "I can't even write bubble sort on a whiteboard" wasn't "I would accidentally write a more efficient algorithm instead" ;)
- jcranmer 7y ago
  I learn algorithms by memorizing their general structure and filling in gaps using the invariants of the process. A selection sort is pulling the largest elements to the end of the list; an insertion sort sorts the first N elements and inserts the next element; a quick sort picks a pivot to divide the list for sorting; mergesort sorts half the list and then merges them; heap sort heapifies the input (this takes me some time to remember how to do efficiently) and then pulls out the top repeatedly. But bubblesort? There's no invariant. Sure, I can tell you that it's this structure: for i = ? .. ?: for j = ? .. ?: i1, i2 = ?, ? if A[i1] < A[i2]: A[i1], A[i2] = A[i2], A[i1] But, with the lack of invariants, I don't know how to fill in the ? correctly. With trial and error, I could write a correct sort from this template. But insertion sort and selection sort also follow this template (as does any other sorting network if you try hard enough), and I can't guarantee that I'd hit bubblesort instead of those.
  - seba_dos1 7y ago
    I don't buy it. Bubble sort is the simplest, the most naive one, you don't even have to remember anything about it. do sorted = true for i = 0 .. n-1: if A[i] > A[i+1]: A[i], A[i+1] = A[i+1], A[i] sorted = false while not sorted That's already a perfectly valid bubble sort. You can then optimize it by noticing that after nth iterations nth elements will already be sorted, and you're done. If you're trying to recall this algorithm from memory by comparing it with other sorting algorithms you've memorized, you're probably doing it wrong, because there's hardly a place for real world usage of bubble sort, so your memory of it is naturally going to fade away. The trick is - you don't even need to memorize it or recall any structure to fit it into. Just imagine an inefficiently bubbling array of numbers in your head and that's it.

eesmith 7y ago

Now I get to be that guy. Your i only needs to go to n-1, and your j can start with i+1. More importantly, what you wrote is a selection sort, not a bubble sort! A bubble sort swaps neighboring terms. Eg, if I interpret the code in 2.1 of https://users.cs.duke.edu/~ola/bubble/bubble.html https://users.cs.duke.edu/~ola/bubble/bubble.html correctly, the 'definitive' version is: for i = n-1..0: for j = 0..i: if arr[j+1] < arr[j]: arr[j], arr[i] = arr[i], arr[j]

dickeytk 7y ago
Fair point. Perhaps it is harder than I thought without looking anything up or testing? At least to get the canonical version written down.
- eesmith 7y ago
  I think it's that "bubble sort" has come to mean "a simple O(N²) sort implementation", of which there are many. But the selection sort just feels more natural than the actual bubble sort. At the very least, selection sort doesn't get my face to scrunch up in a scowl at all those memory movements.