Algorithms Reference

This sheet covers searching, sorting, recursion, and how to say which of two solutions is better.

Preconditions and postconditions — lesson 4

Every algorithm has a precondition (what must be true before it runs) and a postcondition (what it guarantees afterwards). Writing them down is how you find the case that breaks.

// Find target in a sorted array.
// Precondition:  values is sorted ascending.
// Postcondition: returns the index of target, or -1.

Binary search on an unsorted array returns a wrong answer rather than an error. The precondition is the whole reason it works.

Searching — lesson 7

Linear search

Look at each item until one matches or you run out. Precondition: none. This one finds the position of the first temperature below zero. A return inside the loop ends the loop and the function at once, so the return -1 after the loop runs only when nothing matched.

function firstFreezing(temps) {
  for (let i = 0; i < temps.length; i++) {
    if (temps[i] < 0) {
      return i;
    }
  }
  return -1;
}

Binary search

Halve the range each time. Precondition: the array is sorted. This one finds a word in an array of words in alphabetical order.

function findWord(words, wanted) {
  let first = 0;
  let last = words.length - 1;
  while (first <= last) {
    const middle = Math.floor((first + last) / 2);
    if (words[middle] === wanted) {
      return middle;
    }
    if (words[middle] < wanted) {
      first = middle + 1;
    } else {
      last = middle - 1;
    }
  }
  return -1;
}

first <= last, not <: with one item left, first === last, and < would skip it.

Comparing them

Count comparisons, not seconds — a fast computer does not make a bad algorithm good.

Doubling n adds one comparison to binary search and doubles linear search.

Sorting — lesson 7

Lesson 7 teaches insertion sort. Bubble sort and selection sort are not taught; they are here so you can compare their comparison counts with the one you wrote.

Both swap two items with one line, [a[i], a[j]] = [a[j], a[i]]. That is the array destructuring from lesson 2 without const: the right side builds a two-item array, and the left side assigns its values back in the opposite order.

Bubble sort (not taught)

Repeatedly swap neighbours that are out of order.

function bubbleSort(values) {
  const out = [...values];
  for (let pass = 0; pass < out.length - 1; pass++) {
    let swapped = false;
    for (let i = 0; i < out.length - 1 - pass; i++) {
      if (out[i] > out[i + 1]) {
        [out[i], out[i + 1]] = [out[i + 1], out[i]];
        swapped = true;
      }
    }
    if (!swapped) {
      break;          // already sorted; stop early
    }
  }
  return out;
}

Selection sort (not taught)

Find the smallest remaining item, put it next.

function selectionSort(values) {
  const out = [...values];
  for (let i = 0; i < out.length - 1; i++) {
    let min = i;
    for (let j = i + 1; j < out.length; j++) {
      if (out[j] < out[min]) {
        min = j;
      }
    }
    if (min !== i) {
      [out[i], out[min]] = [out[min], out[i]];
    }
  }
  return out;
}

Insertion sort

Take the next item and slide it back into its place. This one sorts words from shortest to longest, so it compares their lengths.

function sortByLength(words) {
  const sorted = [...words];
  for (let pass = 1; pass < sorted.length; pass++) {
    const word = sorted[pass];
    let k = pass;
    while (k > 0 && sorted[k - 1].length > word.length) {
      sorted[k] = sorted[k - 1];
      k--;
    }
    sorted[k] = word;
  }
  return sorted;
}

Comparing them

At n = 1,000 an n² sort does roughly a million comparisons. At n = 10,000, a hundred million.

How to measure

Count operations from inside the algorithm. This is evidence, not opinion.

function bubbleSortCounted(values) {
  let comparisons = 0;
  const out = [...values];
  for (let pass = 0; pass < out.length - 1; pass++) {
    for (let i = 0; i < out.length - 1 - pass; i++) {
      comparisons++;
      if (out[i] > out[i + 1]) {
        [out[i], out[i + 1]] = [out[i + 1], out[i]];
      }
    }
  }
  return { sorted: out, comparisons: comparisons };
}

Order of growth

Order of growth describes how the work grows as the input grows. Constants are ignored, because at large n they stop mattering.

You can read it off the code. One loop over n is O(n), a loop inside a loop, both over n, is O(n²), and halving the range each pass is O(log n).

Two-dimensional arrays — lesson 8

const grid = [
  [1, 2, 3],
  [4, 5, 6]
];
grid[1][2]            // 6   — row 1, column 2
grid.length           // 2   — number of rows
grid[0].length        // 3   — number of columns

for (let row = 0; row < grid.length; row++) {
  for (let col = 0; col < grid[row].length; col++) {
    // grid[row][col] is each cell in turn, row by row
  }
}

To read a grid column by column, put the column loop outside and the row loop inside. Every row must then be the same length, and an empty grid has no grid[0], so handle it first.

Build an empty grid one row at a time, so that every row is a separate array:

const empty = [];
for (let row = 0; row < rows; row++) {
  const cells = [];
  for (let col = 0; col < cols; col++) {
    cells.push(0);
  }
  empty.push(cells);
}

Recursion — lesson 8

A recursive function calls itself. It has two parts, and the base case is written first.

function sumTo(n) {
  if (n <= 0) {
    return 0;                       // BASE CASE — stops the recursion
  }
  const smaller = sumTo(n - 1);     // RECURSIVE CASE — moves toward the base
  return n + smaller;
}
console.log(sumTo(4));   // 10, which is 4 + 3 + 2 + 1

Where it goes wrong

Naive Fibonacci is O(2ⁿ): fib(50) makes about 40 billion calls, a minute or more of work, and fib(60) makes five trillion, which takes hours.

Not taught in class — Level 4 material