📓4.15: Sorting Algorithms

Table of Contents

📖 This page is a condensed version of CSAwesome Topic 4.15

Sorting Algorithms

There are many sorting algorithms to put an array or ArrayList elements in alphabetical or numerical order. We will show these algorithms below for arrays. The three sorting algorithms that you need to know for the AP CSA exam are:

  1. Selection Sort - Select the smallest item from the current location on to the end of the array and swap it with the value at the current position. Do this from index 0 to the array length - 1.

    You don’t have to process the last element in the array, it will already be sorted when you compare the prior element to the last element.

  2. Insertion Sort - Insert the next unsorted element in the already sorted part of the array by moving larger values to the right. Start at index 1 and loop through the entire array.
  3. Merge Sort - Break the elements into two parts and recursively sort each part. An array of one item is sorted (base case). Then merge the two sorted arrays into one.

    Merge Sort will be covered in Unit 10.

Selection Sort

The selection sort that you need to know for the exam starts at index 0 and looks through the entire array keeping track of the index of the smallest value in the array, and then swaps the value at the smallest index with the value at index 0. Then it does the same thing for index 1, then 2, and so on until it reaches the length of the array minus one. At this point the array is sorted in ascending order.

🔍 To identify a Selection Sort look for the following:

  • A nested for loop with the outer loop starting at 0 and ending when the index reaches length - 1
  • The index of the smallest value should start at the outer loop index
  • The inner loop should start at the outer loop index + 1 and iterate through the whole array
  • If the value in the array at the index of the inner loop is less than the value at the smallest index, then reset the smallest index to the index of the inner loop
  • Swap the value at the outer loop index and the smallest value (the one at the smallest value index)

The code for selectionSort below is from the AP CSA course description:

public static void selectionSort(int[] elements) {
    for (int j = 0; j < elements.length - 1; j++) {
        int minIndex = j;
        for (int k = j + 1; k < elements.length; k++) {
            if (elements[k] < elements[minIndex]) {
                minIndex = k;
            }
        }
        int temp = elements[j];
        elements[j] = elements[minIndex];
        elements[minIndex] = temp;
    }
}

👯 Here is a folk dance video that demonstrates the selection sort process:

Insertion Sort

The insertion sort that you need to know for the exam starts at index 1 and inserts the value at index 1 into its correct place in the already sorted part (the part to the left of the current index). It moves any value larger than the value stored in temp to the right, until it either finds the appropriate place to put temp OR gets to the front of the array.

🔍 To identify an Insertion Sort look for the following:

  • An outer for loop that starts at index 1 and iterates through the entire array
  • Storing the element value at the outer loop index in temp
  • Setting the possible index to the outer loop index
  • An inner while loop that loops while the possible index is greater than 0 AND the value in temp is less than the value at the possible index minus one
  • Set the value at the possible index to the one to the left of it (the one at possible index minus one)
  • Decrement the possible index (subtract one from it)
  • When the while loop ends, set the value at the possible index to temp

The code for insertionSort below is from the AP CSA course description:

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

👯 Here is a folk dance video that demonstrates the insertion sort process:

💻 In-Class Activity: Sort Runtimes

  1. Go to
  2. Make sure you SIGN IN!
  3. Complete the Programming Challenge: Sort Runtimes in groups.

⭐️ Summary

  • (AP 4.15.A.1) Selection sort and insertion sort are iterative sorting algorithms that can be used to sort elements in an array or ArrayList.
  • (AP 4.15.A.2) Selection sort repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it into its correct (and final) position in the sorted portion of the list.
  • (AP 4.15.A.3) Insertion sort inserts an element from the unsorted portion of a list into its correct (but not necessarily final) position in the sorted portion of the list by shifting elements of the sorted portion to make room for the new element.
  • Informal run-time comparisons of program code segments can be made using statement execution counts.

Acknowledgement

Content on this page is adapted from Runestone Academy - Barb Ericson, Beryl Hoffman, Peter Seibel.