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:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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 this link

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




12-4-2: 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;
   }
}