Early implementations of this algorithm exhibited its worst-case runtime on sorted arrays, which can be avoided using the “median-of-three” rule. For 10 points each:
[10m] Name this divide-and-conquer algorithm that repeatedly partitions an array about a pivot, moves smaller values to the left of the pivot, and moves larger values to the right of the pivot.
ANSWER: quicksort [or partition-exchange sort; reject “exchange sort”]
[10e] A sorted list admits a search algorithm named for this word that also works by repeated partition. Computer science typically works in a base with this name, which is synonymous with base-2.
ANSWER: binary [accept binary search]
[10h] The parity of k partitions of a string of 2 to the k binary digits is checked in an “extended” error correction code named for this American computer scientist, which is robust when his namesake “distance” is at most 1.
ANSWER: Richard Hamming [accept Hamming code or extended Hamming code; accept Hamming distance]
<Editors, Other Science>