- Inspect all elements in the array to find the smallest.
- Exchange this element with the first entry in the array.
- Now the smallest is first.
- Inspect all elements in the array to find the smallest starting with the second element.
- Exchange this element with the second.
- Continue until all elements are in sorted order.
- (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.)
- Sort the first 2 elements in an array
- 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
- Now 3 elements are sorted
- Keep moving up the array, inserting each element into the ones that are already sorted until all elements are sorted.
- Cut the array in half.
- Recursively sort each half of the array
- Combine the 2 sorted halves together in sorted order.
- (uses temporary array storage to store the parts and merge then back together)
Quick Sort (CS4 AP AB only)
- Choose an element in the array (the pivot)
- Divide the array into 2 parts, part 1 is all values < pivot, part 2 is all values >= pivot.
- Recursively quicksort the parts.
- (does not use an extra array for storage but swaps the values around in the array as it goes)
Blue Book pages 235-246