Time estimate: 45 min.

4.15. Sorting Algorithms¶

There are many sorting algorithms to put an array or ArrayList elements in alphabetic or numerical order. Selection sort and insertion sort are iterative sorting algorithms that can be used to sort elements in an array or ArrayList. We will show these algorithms below for arrays. The three sorting algorithms that you need to know for the AP CSA exam are:

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.
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.
Merge sort breaks 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. MergeSort will be covered in lesson 4.17.

4.15.1. Selection Sort¶

Selection sort usually starts at index 0 and looks through the entire array keeping track of the the index of the smallest value in the array (a findMin algorithm) 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.

Here is a folk dance video that shows the selection sort process.

And a short video that describes how selection sort works.

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 (see line 7 below)
the index of the smallest value should start at the outer loop index (see line 9 below)
the inner loop should start at the outer loop index + 1 and loop through the whole array (see line 10 below)
if the value in the array at the index of the inner loop is less than the value at the smallest index then set the smallest index to the index of the inner loop (see lines 12 - 15)
swap the value at the outer loop index and the smallest value (the one at the smallest value index) (see lines 17-19)

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

Demonstration of selection sort. Click on the Code Lens button or the link below to step through the code.

import java.util.Arrays;

public class SortTest
{
    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;
        }
    }

public static void main(String[] args)
    {
        int[] arr1 = {3, 86, -20, 14, 40};
        System.out.println(Arrays.toString(arr1));
        selectionSort(arr1);
        System.out.println(Arrays.toString(arr1));
    }
}

====
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{
    @Test
    public void testMain() throws IOException
    {
        String output = getMethodOutput("main");
        String expect = "[3, 86, -20, 14, 40]\n[-20, 3, 14, 40, 86]";
        boolean passed = getResults(expect, output, "Expected output from main", true);
        assertTrue(passed);
    }
}

To see this executing using the Java Visualizer click on the following SelectionSort

Check Your Understanding

4-15-4: Under what condition will a selection sort execute faster?

If the data is already sorted in ascending order
How would this be faster? Look at the code.
If the data is already sorted in descending order
How would this be faster? Look at the code.
It will always take the same amount of time to execute
A selection sort always does the same number of comparisons and always takes the same time to execute regardless of the order of the data.

4-15-5: This method should sort the numbers in the passed array into ascending order. But, it does not work. Which of the following lines is wrong?

public static void selectionSort(int[] elements)
{
  for (int j = 0; j < elements.length − 1; j++)      // line 1
  {
     int minIndex = j;                               // line 2
     for (int k = 0; k < elements.length; k++)       // line 3
     {
        if (elements[k] < elements[minIndex])        // line 4
        {
           minIndex = k;                             // line 5
        }
     }
     int temp = elements[j];
     elements[j] = elements[minIndex];
     elements[minIndex] = temp;
   }
}

line 1
The outer loop starts at 0 and ends when it reaches the length - 1.
line 2
The min index should be set to the outer loop index before the start of the inner loop.
line 3
The inner loop should start at the outer loop index + 1.
line 4
You should compare the element at the inner loop index to the element at the min index to see if it is smaller.
line 5
You should save the new min index as the inner loop index.

You can step through the code above by clicking on the following Ex-12-4-2.

4.15.2. Insertion Sort¶

Insertion sort usually 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.

Here is a folk dance video that shows the insertion sort process.

And a short video that describes how insertion sort works.

To identify an insertion sort look for the following:

an outer for loop that starts at 1 and loops through the entire array (see line 7)
storing the element value at the outer loop index in temp (see line 9)
setting the possible index to the outer loop index (see line 10)
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 (see line 11)
set the value at the possible index to the one to the left of it (the one at possible index minus one) (see line 13)
decrement the possible index (subtract one from it) (see line 14)
when the while loop ends set the value at the possible index to temp (see line 16)

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

Demonstration of insertion sort. Click on the Code Lens button or the link below to step through the code.

import java.util.Arrays;

public class SortTest
{
    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;
        }
    }

public static void main(String[] args)
    {
        int[] arr1 = {3, 86, -20, 14, 40};
        System.out.println(Arrays.toString(arr1));
        insertionSort(arr1);
        System.out.println(Arrays.toString(arr1));
    }
}

====
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

To see this executing using the Java Visualizer click on the following Insertion-Sort

Check Your Understanding

4-15-9: Under what condition will an insertion sort execute faster?

If the data is already sorted in ascending order
If the data is already sorted in the correct order you don't need to move any values.
If the data is already sorted in descending order
This would actually result in the longest execution.
It will always take the same amount of time to execute
This would be true if it was a selection sort.

4-15-10: This method should sort the numbers in the passed array into ascending order. But, it does not work. Which of the following lines is wrong?

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

line 1
It should loop through the entire array.
line 2
The value at the outer loop index should be stored in temp.
line 3
The possible index should be set to the outer loop index before the inner loop executes.
line 4
Loop while the possible index is greater than 0 and the temp value is less than the value at the possible index minus one.
line 5
Move the value at possible index minus one to the possible index (move to the right).

You can step through the code above by clicking on the following Visualization.

4.15.3. Coding Challenge : Sort Runtimes¶

Selection sort and Insertion sort have similar runtimes. They both have nested loops that run through the data of size n approximately n squared times. However, they perform differently on some data.

In the Active code windows for Selection sort and Insertion sort above, add in a counter and increment it inside the inner loop to count the number of iterations. Add in print statements that will print the counter value after the loops. Run the code on the following data and record the runtimes in this Google document (login to Google to make your own copy) also seen below.

4-15-11: Compare the runtimes of selection and insertion sort on the same data. There should be some data where one performed better than the other. Can you explain why this is? Trace through the code to figure out why. Discuss in pairs or groups. Using the space provided below, summarize the key discussion points and include a link to your Google document with the table of runtimes.

4.15.4. 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.

4.15.5. Search/Sort Multiple-Choice Exercises¶

Try the following multiple-choice exercises to practice search and sort algorithms: Search/Sort Multiple-Choice Exercises.

You have attempted of activities on this page

Before you keep reading...