3 ms·
I love this paragraph from the paper: There is nothing good about this algorithm. It is slow – the algorithm obviously runs in Θ(n2) time, whether worst-case,
by jp57 2y ago
I love this paragraph from the paper:
There is nothing good about this algorithm. It is slow – the algorithm
obviously runs in Θ(n2) time, whether worst-case, average-case or best-case.
It unnecessarily compares all pairs of positions, twice (but see Section 3).
There seems to be no intuition behind it, and its correctness is not entirely
obvious. You certainly do not want to use it as a first example to introduce
students to sorting algorithms. It is not stable, does not work well for
external sorting, cannot sort inputs arriving online, and does not benefit
from partially sorted inputs. Its only appeal may be its simplicity, in terms
of lines of code and the “symmetry” of the two loops.
- teach 2y agoI used to teach this to beginners all the time. I called it "exchange sort", though I'm not sure where I ever got that name from. Beginners to sorting are often still somewhat struggling with for loops (especially the three-part C kind), struggling with indexing an array, struggling with swaps. It's overwhelming. This is kind-of like pseudocode for a simple sort -- it has the same rough outline, but no tricky bits. It allows them to get their brains around the basic algorithm, and only after that you trace through an execution on the board to show them that it wastes a lot of time moving things around. Then you can show them insertion sort as an optimization, and from that move on to fancier ones.
- justinpombrio 2y agoCan you give a reference to your teaching materials? The way this sort works is bizarre enough that I'm curious what you said about it. (Also to verify that this is actually the algorithm you taught, given how many other people thought it was something else.)
- wrsh07 2y agoNote that they define algorithm 2 (see figure of said name) as Exchange Sort, which is distinct from the algorithm they present
- jp57 2y agoThe sort in the OP isn't Exchange Sort, though. In exchange sort the inner loop runs from i+1 to N, not from 0 to N, and the swap order is transposed.
- teach 2y agoThen I guess I called it exchange sort incorrectly. I'm certain this is the code I taught them -- both loops went from 0 to (less than) N.