This book is now obsolete Please use CSAwesome instead.

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

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

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 CS A course description.

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

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

13-4-3: 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.

13-4-4: 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.

You have attempted of activities on this page