4.15 Sorting Algorithms

1. Two iterative sorts

Selection sort and insertion sort are iterative sorting algorithms: they use loops (not recursion) and can sort the elements of an array or an ArrayList 4.15.A.1. Both split the list into a sorted portion at the front and an unsorted portion after it. Each pass of the outer loop makes the sorted portion one element longer, so a list of n elements needs n - 1 passes.

Every example on this page sorts the same six race times (in seconds) into increasing order:

index	0	1	2	3	4	5
value	29	12	41	7	18	33

2. Selection sort

Selection sort repeatedly selects the smallest element from the unsorted portion and swaps it into its correct and final position at the end of the sorted portion 4.15.A.2. (A version that selects the largest element and swaps it to the back works the same way.)

public static void selectionSort(int[] arr)
{
    for (int i = 0; i < arr.length - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
        System.out.println("pass " + (i + 1) + ": " + Arrays.toString(arr));
    }
}

int[] times = {29, 12, 41, 7, 18, 33};
selectionSort(times);

Output:

pass 1: [7, 12, 41, 29, 18, 33]
pass 2: [7, 12, 41, 29, 18, 33]
pass 3: [7, 12, 18, 29, 41, 33]
pass 4: [7, 12, 18, 29, 41, 33]
pass 5: [7, 12, 18, 29, 33, 41]

(Arrays.toString is only used here to show the array; it is not part of the AP® Java Quick Reference.)

Pass by pass (bold = sorted portion, which is final):

Pass	Minimum found	Swap	Array after the pass	Comparisons
start			29 12 41 7 18 33
1	7 (index 3)	index 0 and 3	7 12 41 29 18 33	5
2	12 (index 1)	with itself	7 12 41 29 18 33	4
3	18 (index 4)	index 2 and 4	7 12 18 29 41 33	3
4	29 (index 3)	with itself	7 12 18 29 41 33	2
5	33 (index 5)	index 4 and 5	7 12 18 29 33 41	1

Total: 5 + 4 + 3 + 2 + 1 = 15 comparisons. For n elements selection sort always makes n(n - 1) / 2 comparisons, even when the list starts sorted, because it must check every unsorted element to be sure it has the minimum.

Watch out: on passes 2 and 4 the minimum was already in place, so the array did not change. A question asking for “the array after pass 2” expects the same array as after pass 1.

3. Insertion sort

Insertion sort takes the first element of the unsorted portion and inserts it into its correct, but not necessarily final, position in the sorted portion. It makes room by shifting the larger elements of the sorted portion one place to the right 4.15.A.3.

public static void insertionSort(int[] arr)
{
    for (int i = 1; i < arr.length; i++)
    {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];   // shift right
            j--;
        }
        arr[j + 1] = key;          // insert into the gap
        System.out.println("pass " + i + ": " + Arrays.toString(arr));
    }
}

int[] times = {29, 12, 41, 7, 18, 33};
insertionSort(times);

Output:

pass 1: [12, 29, 41, 7, 18, 33]
pass 2: [12, 29, 41, 7, 18, 33]
pass 3: [7, 12, 29, 41, 18, 33]
pass 4: [7, 12, 18, 29, 41, 33]
pass 5: [7, 12, 18, 29, 33, 41]

Pass by pass (bold = sorted portion, which is sorted but not final):

Pass	Element inserted (key)	Elements shifted right	Array after the pass	Comparisons (arr[j] > key)
start			29 12 41 7 18 33
1	12	29	12 29 41 7 18 33	1
2	41	none	12 29 41 7 18 33	1
3	7	41, 29, 12	7 12 29 41 18 33	3
4	18	41, 29	7 12 18 29 41 33	3
5	33	41	7 12 18 29 33 41	2

Total: 1 + 1 + 3 + 3 + 2 = 10 comparisons. In pass 1, 12 and 29 are in order with each other, but neither is final: on pass 3, the value 7 pushes both of them right.

Watch out: on pass 3 the loop stops because j becomes -1, not because of a comparison. The && short-circuits, so arr[-1] is never read.

4. Sorting an ArrayList

Both algorithms work on an ArrayList too 4.15.A.1. Replace arr[i] with get(i), assignments with set(i, value) and length with size().

ArrayList<String> names = new ArrayList<String>();
names.add("Mia");
names.add("Ali");
names.add("Zoe");
names.add("Ben");

// selection sort, alphabetical order
for (int i = 0; i < names.size() - 1; i++)
{
    int minIndex = i;
    for (int j = i + 1; j < names.size(); j++)
    {
        if (names.get(j).compareTo(names.get(minIndex)) < 0)
        {
            minIndex = j;
        }
    }
    String temp = names.get(i);
    names.set(i, names.get(minIndex));
    names.set(minIndex, temp);
}
System.out.println(names);

Output:

[Ali, Ben, Mia, Zoe]

5. Comparing the two sorts informally

Count comparisons to compare the algorithms informally. The starting order matters for insertion sort but not for selection sort.

public static int selectionComparisons(int[] arr)
{
    int count = 0;
    for (int i = 0; i < arr.length - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++)
        {
            count++;
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return count;
}

public static int insertionComparisons(int[] arr)
{
    int count = 0;
    for (int i = 1; i < arr.length; i++)
    {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0)
        {
            count++;
            if (arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }
            else
            {
                break;
            }
        }
        arr[j + 1] = key;
    }
    return count;
}

int[] sorted = {1, 2, 3, 4, 5, 6};
int[] reversed = {6, 5, 4, 3, 2, 1};
System.out.println("selection, sorted:   " + selectionComparisons(new int[] {1, 2, 3, 4, 5, 6}));
System.out.println("selection, reversed: " + selectionComparisons(new int[] {6, 5, 4, 3, 2, 1}));
System.out.println("insertion, sorted:   " + insertionComparisons(sorted));
System.out.println("insertion, reversed: " + insertionComparisons(reversed));

Output:

selection, sorted:   15
selection, reversed: 15
insertion, sorted:   5
insertion, reversed: 15

(The break statement here only makes counting easy; it is not needed for the AP® exam.)

	Selection sort	Insertion sort
Each pass	select the minimum of the unsorted portion, swap it in	insert the next element, shifting larger ones right
Is the position final after the pass?	yes 4.15.A.2	not necessarily 4.15.A.3
Comparisons, 6 elements already sorted	15	5
Comparisons, 6 elements in reverse order	15	15
Comparisons, n elements	always n(n - 1) / 2	from n - 1 up to n(n - 1) / 2

Topic 4.17 adds a third sort, merge sort, which is recursive.