4.15 - Sorting Algorithms

Selection sort and insertion sort are two iterative sorting algorithms.

Selection sort repeatedly finds the smallest (or largest) element in the unsorted part of the list and swaps it into its final correct position.


int[] nums = {5, 2, 8, 1, 9};

for (int i = 0; i < nums.length - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] < nums[minIndex]) {
            minIndex = j;
        }
    }
    // swap the found minimum into its correct position
    int temp = nums[minIndex];
    nums[minIndex] = nums[i];
    nums[i] = temp;
}

Insertion sort takes an element from the unsorted portion and inserts it into its correct position within the already-sorted portion, shifting elements over to make room.


int[] nums = {5, 2, 8, 1, 9};

for (int i = 1; i < nums.length; i++) {
    int key = nums[i];
    int j = i - 1;
    while (j >= 0 && nums[j] > key) {
        nums[j + 1] = nums[j]; // shift elements right to make room
        j--;
    }
    nums[j + 1] = key;
}

The figure traces both sorts on {5, 2, 8, 1, 9}. Things to notice:

Selection sort puts one value in its final spot each pass. After pass 1, the 1 is at index 0 and never moves again. After k passes, the first k elements are the k smallest values in the whole array, in order.

Insertion sort puts each value in its correct but not necessarily final spot. In pass 1, the 2 moves to index 0, but in pass 3 the 1 gets inserted in front of it and pushes the 2 to index 1. After k passes, the first k + 1 elements are the array’s original first k + 1 values, sorted among themselves.

Both make n - 1 passes for an array of n elements (4 passes here).

That gives a quick way to tell them apart on a multiple-choice question. If the front of the array holds the smallest values overall, it’s selection sort. If the front holds the original first few values in sorted order, with smaller values still waiting later in the array, it’s insertion sort.

Insertion sort does very little work on an array that’s already sorted or nearly sorted, since each new value barely has to move. Selection sort always scans the whole unsorted part on every pass, no matter what.

Both sorts work on an ArrayList too, using get and set in place of brackets. For an ArrayList<Integer> named list, the selection sort swap becomes:


int temp = list.get(i);
list.set(i, list.get(minIndex));
list.set(minIndex, temp);

Back Next