Aim for FiveComputer Science A

Unit 4 · Topic 4.15

4.15 Sorting Algorithms

Selection sort and insertion sort put a list in order one pass at a time. You won't be asked to invent them, but you do need to trace them: say what the array looks like after each pass. This topic shows the code for both and how their passes differ.

Key terms

  • selection sort
  • insertion sort
  • swap
  • shift
  • pass

Selection sort

Selection sort splits the array into a sorted part at the front and an unsorted part after it. On each pass, it finds the smallest element in the unsorted part and swaps it into the first unsorted position. Once an element is placed there, it's in its final position and never moves again.

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; } }

For an array of length n, it makes n - 1 passes. A swap can move an element from the front of the unsorted part far to the back, and sometimes the smallest element is already in place, so it gets "swapped" with itself. Sorting into descending order just means selecting the largest element each pass instead.

Insertion sort

Insertion sort also builds a sorted part at the front, but it grows by taking the next element and inserting it where it belongs among the elements already sorted. Larger sorted elements shift one place right to make room.

public static void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int temp = arr[i]; int j = i; while (j > 0 && arr[j - 1] > temp) { arr[j] = arr[j - 1]; j--; } arr[j] = temp; } }

An element's position is correct relative to the sorted part, but not necessarily final: a smaller element arriving later can push it further right.

Telling them apart in a trace

If the front of the array after each pass holds the smallest values of the whole array, in order, it's selection sort. If the front holds the first few original values rearranged into order, it's insertion sort. After two passes on {5, 2, 9, 1, 6}, selection sort has 1, 2 at the front, the two smallest overall. Insertion sort has 2, 5, 9, which are just the first three original values in order.

Both make more checks on bigger arrays. Selection sort makes the same number of comparisons for any array of a given length, even one that's already sorted. Insertion sort does very little work on data that's already nearly sorted, because each element barely needs to move.

Not on the exam

Selection sort, insertion sort and merge sort (4.17) are the only sorts in the course. You won't be tested on other sorting algorithms.

Worked examples

Try each one yourself first, then open the solution.

  1. Example 1

    Tracing selection sort

    This version of selection sort prints the array after each pass. What does selectionSortTrace print for {5, 2, 9, 1, 6}?public static void selectionSortTrace(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; for (int v : arr) { System.out.print(v + " "); } System.out.println(); } }

    Show the solution
    1. Step 1: Pass 1 (i = 0): the smallest of all five is 1, at index 3. Swap it with the 5 at index 0: 1 2 9 5 6.
    2. Step 2: Pass 2 (i = 1): the smallest of 2, 9, 5, 6 is 2, already at index 1. It swaps with itself: 1 2 9 5 6.
    3. Step 3: Pass 3 (i = 2): the smallest of 9, 5, 6 is 5, at index 3. Swap with the 9: 1 2 5 9 6.
    4. Step 4: Pass 4 (i = 3): the smaller of 9 and 6 is 6. Swap: 1 2 5 6 9. The last element is automatically in place, so there's no fifth pass.

    Answer: Four lines: 1 2 9 5 6, 1 2 9 5 6, 1 2 5 9 6, 1 2 5 6 9.

  2. Example 2

    Tracing insertion sort

    This version of insertion sort prints the array after each pass. What does insertionSortTrace print for {5, 2, 9, 1, 6}?public static void insertionSortTrace(int[] arr) { for (int i = 1; i < arr.length; i++) { int temp = arr[i]; int j = i; while (j > 0 && arr[j - 1] > temp) { arr[j] = arr[j - 1]; j--; } arr[j] = temp; for (int v : arr) { System.out.print(v + " "); } System.out.println(); } }

    Show the solution
    1. Step 1: Pass 1 (i = 1): take the 2. The 5 is bigger, so it shifts right, and the 2 goes in front: 2 5 9 1 6.
    2. Step 2: Pass 2 (i = 2): take the 9. The 5 before it is smaller, so nothing moves: 2 5 9 1 6.
    3. Step 3: Pass 3 (i = 3): take the 1. The 9, 5 and 2 are all bigger, so each shifts right, and the 1 goes to index 0: 1 2 5 9 6.
    4. Step 4: Pass 4 (i = 4): take the 6. The 9 shifts right; the 5 is smaller, so the 6 goes after it: 1 2 5 6 9.

    Answer: Four lines: 2 5 9 1 6, 2 5 9 1 6, 1 2 5 9 6, 1 2 5 6 9.

Common mistakes

  • Mixing up the two sorts. Selection sort picks the smallest remaining element and swaps; insertion sort takes the next element and shifts others to slide it in.
  • Forgetting that a selection sort pass can swap an element with itself, leaving the array unchanged for that pass.
  • Thinking insertion sort's front elements are in their final places. They're sorted among themselves, but later elements can still move them.

On the exam

  • Expect questions that show an array after one, two or three passes and ask which sort produced it, or what the array looks like after a given pass. Trace one pass at a time, writing the whole array each time.

Connected topics

Videos

Check yourself

4 questions on 4.15 Sorting Algorithms. Pick an answer to see if you got it, and why.

Question 1 of 4

Consider the following method.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; } }Assume arr is {5, 2, 9, 1, 7} before selectionSort(arr) is called. What are the contents of arr after the outer loop has finished three passes (i = 0, 1 and 2)?

Question 2 of 4

Consider the following method.public static void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int temp = arr[i]; int j = i; while (j > 0 && arr[j - 1] > temp) { arr[j] = arr[j - 1]; j--; } arr[j] = temp; } }Assume arr is {6, 3, 8, 1, 4} before insertionSort(arr) is called. What are the contents of arr after the outer loop has finished three passes (i = 1, 2 and 3)?

Question 3 of 4

Which of the following statements about selection sort and insertion sort, sorting from smallest to largest, is true?

Question 4 of 4

Consider the selectionSort method shown below.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; } }When selectionSort is called on an array of 5 elements, how many times is the comparison arr[j] < arr[minIndex] evaluated?

0 of 4 answered