3 ms·

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

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.

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.