Programmers can’t write algorithms without help

Re:Programmers can’t write algorithms without help by jcranmer on Monday November 04, 2019 @01:40PM (#21444848)

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.

[ Parent | on HN ]

Re:Programmers can’t write algorithms without help by seba_dos1 on Tuesday November 05, 2019 @09:45AM (#21452776)

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.

[ Parent | on HN ]