Sorting: selection and insertion sort

Putting an array in order

• Sorting means putting the values of an array in order, usually from small to large.
• On the AP CSA exam you must be able to write and trace two sorts: selection sort and insertion sort.
• You also need to trace (but not write) a third sort: merge sort. We look at all three here.

Selection sort: the idea

• Walk through the array from left to right.
• At each spot i, find the smallest value in the part that is still unsorted (from i to the end).
• Swap that smallest value into spot i. Now 0..i is sorted.
• Repeat until the whole array is in order.

public class Sorter {
    public static void selectionSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;                       // index of smallest so far
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j;                   // found a smaller value
                }
            }
            int temp = a[min];                 // swap a[i] and a[min]
            a[min] = a[i];
            a[i] = temp;
        }
    }
}

Selection sort: a trace

• Let us sort {5, 2, 4, 1, 3}. The bold part is already sorted.
• Each pass picks the smallest value from the rest and swaps it to the front.

start:        [5, 2, 4, 1, 3]
i=0  smallest=1 → swap a[0],a[3]:   [1 | 2, 4, 5, 3]
i=1  smallest is already 2 → no move: [1, 2 | 4, 5, 3]
i=2  smallest=3 → swap a[2],a[4]:   [1, 2, 3 | 5, 4]
i=3  smallest=4 → swap a[3],a[4]:   [1, 2, 3, 4 | 5]
done:         [1, 2, 3, 4, 5]

Insertion sort: the idea

• Think of holding playing cards and adding one card at a time into the right place.
• Start at index 1. Call this value the key.
• Slide bigger values on the left one step to the right, until the key fits.
• Drop the key into the gap. Now everything to the left is sorted.

public class Sorter {
    public static void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i];                    // the value to place
            int j = i - 1;
            while (j >= 0 && a[j] > key) {     // shift bigger values right
                a[j + 1] = a[j];
                j = j - 1;
            }
            a[j + 1] = key;                    // drop key into the gap
        }
    }
}

Insertion sort: a trace

• Sort {5, 2, 4, 1, 3} again. The bold part stays sorted as we go.
• The key is the value we are inserting on each pass.

start:           [5, 2, 4, 1, 3]
i=1 key=2 → shift 5 right, place 2:  [2, 5 | 4, 1, 3]
i=2 key=4 → shift 5 right, place 4:  [2, 4, 5 | 1, 3]
i=3 key=1 → shift 5,4,2 right, place 1: [1, 2, 4, 5 | 3]
i=4 key=3 → shift 5,4 right, place 3:   [1, 2, 3, 4, 5]
done:            [1, 2, 3, 4, 5]

Merge sort: trace only

• Merge sort uses recursion (lesson 15). You do not write it on the exam, but you must trace it.
• Split the array in half again and again, until each piece has one value.
• Merge pairs of pieces back together, always keeping them in order.

Merge sort: a trace

• One value is already "sorted". Merging two sorted pieces gives a bigger sorted piece.

split:   [5, 2, 4, 1]
         [5, 2]      [4, 1]
         [5] [2]     [4] [1]
merge:   [2, 5]      [1, 4]
merge:   [1, 2, 4, 5]

• Selection and insertion sort are slow on big arrays (they do about n² steps).
• Merge sort is faster on big arrays (about n·log n steps). That is why it matters.

Common mistakes

• Selection and insertion sort are both O(n²).
• Trace a small array by hand to check your sort.

Now you try

• Each task gives you a method skeleton with a TODO. Sort the array in place (change a itself).
• A hidden Harness sorts several arrays and checks the result.
• Press Run to compile, then Check answer.