Selection Sort

  1. Inspect all elements in the array to find the smallest.
  2. Exchange this element with the first entry in the array.
  3. Now the smallest is first.
  4. Inspect all elements in the array to find the smallest starting with the second element.
  5. Exchange this element with the second.
  6. Continue until all elements are in sorted order.
  7. (this can also be done in the opposite order, start by finding the highest value and placing it at the end of the array, etc.)

Insertion Sort

  1. Sort the first 2 elements in an array
  2. Compare the 3rd element to the 2nd, if it's smaller, swap them, compare it to the 1st element, if it's smaller swap them
  3. Now 3 elements are sorted
  4. Keep moving up the array, inserting each element into the ones that are already sorted until all elements are sorted.

Merge Sort

  1. Cut the array in half.
  2. Recursively sort each half of the array
  3. Combine the 2 sorted halves together in sorted order.
  4. (uses temporary array storage to store the parts and merge then back together)

Quick Sort (CS4 AP AB only)

  1. Choose an element in the array (the pivot)
  2. Divide the array into 2 parts, part 1 is all values < pivot, part 2 is all values >= pivot.
  3. Recursively quicksort the parts.
  4. (does not use an extra array for storage but swaps the values around in the array as it goes)

Blue Book pages 235-246