4.15 Sorting Algorithms · CSA Exam Prep

Jump to topic

Unit 4 · Data Collections · Topic 4.15

Sorting Algorithms

Skill 3.BSkill 4.ASkill 4.B

Big idea: Selection sort finds the smallest remaining item and swaps it into place. Insertion sort takes the next item and slides it back into the sorted part. Exam questions ask what the array looks like after a few passes.

Learning objectives

Determine the result of executing each step of sorting algorithms to sort the elements of a collection.

Selection sort

Each pass finds the smallest item in the unsorted part and swaps it into its final position.

Code

int[] a = {5, 3, 8, 1, 6};
for (int i = 0; i < a.length - 1; i++) {
  int min = i;
  for (int j = i + 1; j < a.length; j++) {
    if (a[j] < a[min]) min = j;
  }
  int temp = a[i];
  a[i] = a[min];
  a[min] = temp;
  System.out.println("pass " + (i + 1) + ": " + Arrays.toString(a));
}

Output

pass 1: [1, 3, 8, 5, 6]
pass 2: [1, 3, 8, 5, 6]
pass 3: [1, 3, 5, 8, 6]
pass 4: [1, 3, 5, 6, 8]

Insertion sort

Each pass takes the next unsorted item and shifts larger sorted items right to make room. The front part is sorted among itself but may still change later.

Code

int[] a = {5, 3, 8, 1, 6};
for (int i = 1; i < a.length; i++) {
  int key = a[i];
  int j = i - 1;
  while (j >= 0 && a[j] > key) {
    a[j + 1] = a[j];
    j--;
  }
  a[j + 1] = key;
  System.out.println("pass " + i + ": " + Arrays.toString(a));
}

Output

pass 1: [3, 5, 8, 1, 6]
pass 2: [3, 5, 8, 1, 6]
pass 3: [1, 3, 5, 8, 6]
pass 4: [1, 3, 5, 6, 8]

Comparing them

	Selection sort	Insertion sort
After pass k	First k items are the k smallest, in final order	First k + 1 items are sorted among themselves
Already-sorted input	Same number of comparisons	Very fast: one comparison per pass
Work per pass	Many comparisons, one swap	Comparisons and shifts until the spot is found

Key points

Selection and insertion sort are iterative sorts for arrays and ArrayLists.
Selection sort swaps the smallest unsorted item into its final position each pass.
Insertion sort inserts the next item into its correct, but not necessarily final, position.

Watch out

After k passes of selection sort, the first k items are the k smallest in final order.
After k passes of insertion sort, the first k + 1 items are sorted among themselves only.

Quick check

After one pass of selection sort on {9, 4, 7, 2}, what is the array?

Show answer

{2, 4, 7, 9}. 2 swaps with 9.

Practice 4.15 (11 questions)