Selection sort algorithm & trace
Selection sort logically partitions the array into 2 parts. We’ll use a pipe character (|) to represent the partition. (The partition is a logical structure. Nothing is physically inserted into the array.)
- Everything to the left of the
|is sorted and is in its final position. - Everything to the right of the
|is unchecked.
With each pass, selection sort finds the minimum in the unchecked part. Selection sort swaps the minimum in the unchecked part with the first element in the unchecked part.
Before the first pass
[ | 71 86 79 36 78 35 75 86 24 11]
The partition starts before the first element. The statements above are both true (since there is nothing to the left of the |).
Pass 1
After finding the minimum but before swapping
[ | 71 86 79 36 78 35 75 86 24 11]
^ minimum
Selection sort finds the smallest value in the unchecked part of the array, which is 11.
After swapping
[11 | 86 79 36 78 35 75 86 24 71]
^ swapped ^
The algorithm swaps the smallest value in the unchecked part with the first value in the unchecked part, which was 71.
Pass 2
After finding the minimum but before swapping
[11 | 86 79 36 78 35 75 86 24 71]
^ minimum
The minimum in the unchecked part of the array is 24.
After swapping
[11 | 24 79 36 78 35 75 86 86 71]
^ swapped ^
24 is swapped with the first value in the unchecked part, which was 71.
Remaining passes
[11 24 35 | 36 78 79 75 86 86 71]
[11 24 35 36 | 78 79 75 86 86 71]
[11 24 35 36 71 | 79 75 86 86 78]
[11 24 35 36 71 75 | 79 86 86 78]
[11 24 35 36 71 75 78 | 86 86 79]
[11 24 35 36 71 75 78 79 | 86 86]
[11 24 35 36 71 75 78 79 86 | 86]
The process repeats until only 1 element remains in the unchecked part. If every other element in the array is in its final position, the last element must also be in its final position. (This array contains the value 86 twice, but that makes no difference.)
Note that selection sort does NOT copy the array. The array is copied here only to show the progression.
The statements at the top of the page are true following each pass through the array.
Selection sort skips the last element. Insertion sort skips the first element.
Selection sort implementation
public static void sort(int[] arr)
{
for(int i = 0; i < arr.length - 1; i++)
{
int minIndex = i;
for(int j = i + 1; j < arr.length; j++)
if(arr[j] < arr[minIndex])
minIndex = j;
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
Selection sort is typically implemented with a pair of for loops, one nested inside the other. The inner loop is responsible for finding the index of the minimum in the unchecked part. The outer loop swaps the minimum with the first value in the unchecked part and moves the partion.
The 3 lines for the swap are sometimes extracted into a swap method.
Selection sort variants
Sorting and searching is used on the AP CS A Exam to ask questions more complex than would be reasonable without prerequisite knowledge. The expectation is that you know each of the 5 algorithms (selection sort, insertion sort, merge sort, sequential/linear search, and binary search) in detail. You may be expected to:
- identify which of the algorithms a piece of code represents.
- determine if a piece of code correctly implements one of the algorithms.
- determine what effect a variation has on the algorithm (ex: breaks it, sorts it backwards).
Several variants of selection sort are presented below. Your goal should not be to memorize the variants, but rather to use them to better understand the algorithm. You must be able to reason about how changes to the algorithm affect the result and the number of statements executed.
Loop directions
Reversed inner loop (works)
public static void sort(int[] arr)
{
for(int i = 0; i < arr.length - 1; i++)
{
int minIndex = i;
for(int j = arr.length - 1; j > i; j--)
if(arr[j] < arr[minIndex])
minIndex = j;
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
In this variant, the inner loop traverses the same elements but in the opposite order. This variant sorts the array in the same order (increasing, non-decreasing, smallest to largest) as the orignal implementation.
The inner loop is responsible for finding the index of the minimum in the unchecked part of the array. The order in which the elements are visited does not matter.
Reversed outer loop (does not work)
public static void sort(int[] arr)
{
for(int i = arr.length - 1; i > 0; i--)
{
int minIndex = i;
for(int j = i + 1; j < arr.length; j++)
if(arr[j] < arr[minIndex])
minIndex = j;
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
In this variant, the outer loop runs from right to left. The problem is the inner loop. When the outer loop ran from left to right, the unchecked part of the array was to the right of the partition. In this variant, the unchecked part is to the left of the partition. Since the inner loop still runs through the right side, the variant does not work.
If the inner loop was changed to run through the left side of the array (as below), the variant would (correctly) sort in the opposite order (decreasing, non-increasing, largest to smallest). As discussed above, the order in which the inner loop visits the elements does not matter. The specific elements the inner loop visits do matter.
for(int j = 0; j < i; j++)
If the code was also modified to find the index of the maximum, the array would be sorted in the original order.
Two line swap (works)
public static void sortVariant(int[] arr)
{
for(int i = 0; i < arr.length - 1; i++)
{
int min = arr[i];
int minIndex = i;
for(int j = i + 1; j < arr.length; j++)
{
if(arr[j] < min)
{
min = arr[j];
minIndex = j;
}
}
arr[minIndex] = arr[i];
arr[i] = min;
}
}
This variant handles swapping elements with 2 lines, instead of the usual 3. The variant stores both the value of the minimum (min) and its index (minIndex). The variable min serves the purpose of the usual temp variable.
This variant sometimes confuses students who look for swap code to distinguish selection sort from insertion sort. The most reliable way to distinguish selection sort from insertion sort is that the inner loop in selection sort does not modify the array.
while loops (works)
public static void sort(int[] arr)
{
int i = 0;
while(i < arr.length - 1)
{
int minIndex = i;
int j = i + 1;
while(j < arr.length)
{
if(arr[j] < arr[minIndex])
minIndex = j;
j++;
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
i++;
}
}
Any for loop can be trivially converted to a while loop. Other than making it more difficult to identify the algorithm, there is nothing interesting about this variant.
Converting the inner loop of insertion sort to a for loop would be awkward. This means that a sort algorithm with nested for loops on the AP CS A Exam is most likely selection sort. The converse is not necessarily true, as this variant demonstrates.
Reliable ways to distinguish selection sort from insertion sort include the method discussed in the previous variant as well as determining that the algorithm swaps elements (even if disguised). Insertion sort does not swap elements.
Recursive implementation (works)
// computes the index of the minimum value in
// arr[startIndex] ... arr[arr.length - 1]
private static int findIndexOfMin(int[] arr, int startIndex)
{
if(startIndex == arr.length - 1)
return startIndex;
int minIndexOfRest = findIndexOfMin(arr, startIndex + 1);
if(arr[startIndex] < arr[minIndexOfRest])
return startIndex;
else
return minIndexOfRest;
}
private static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// sorts arr[startIndex] ... arr[arr.length - 1]
private static void sort(int[] arr, int startIndex)
{
if(startIndex >= arr.length - 1)
return;
int minIndex = findIndexOfMin(arr, startIndex);
swap(arr, startIndex, minIndex);
sort(arr, startIndex + 1);
}
public static void sort(int[] arr)
{
sort(arr, 0);
}
This variant uses 3 private helper methods and a public method:
findIndexOfMinfinds the index of the minimum in the unchecked part of the array. It does this recursively.swapis self explanatory.sort(int[], int)is the private recursive helper method forsort(int[]).sort(int[], int)recursively sorts the part of the array starting at its parameterstartIndex.sort(int[])is the public method. It calls the recursive helper method.sort(int[])exists because this is the appropriate public method header for a sort method.
It is unlikely that this variant would be featured on the AP CS A Exam. The variant is presented here to improve understanding of the algorithm and as a demonstration of recursion. The sort(int[]) method shows the selection sort algorithm elegantly.
- Find the index of the minimum in the unchecked part.
- Swap the minimum with the first value in the unchecked part.
- Sort the rest of the array.
Sorting into new ArrayList<String> (works)
public static ArrayList<String> sort(ArrayList<String> list)
{
ArrayList<String> sortedList = new ArrayList<String>();
while(list.size() > 1)
{
int minIndex = 0;
for(int j = 1; j < list.size(); j++)
if(list.get(j).compareTo(list.get(minIndex)) < 0)
minIndex = j;
sortedList.add(list.remove(minIndex));
}
sortedList.add(list.remove(0));
return sortedList;
}
Instead of sorting list in place, this variant removes the elements from list and returns a new list containing the same elements but in sorted order. This variant is unlikely to be used in practice due to hidden complexity (the expensive calls to remove) and other issues. It demonstrates the algorithm, the use of compareTo, and use of the return value from the ArrayList method remove.
Since the elements are removed from list and added to sortedList, the code to find the index of the minimum runs through all of list. All elements remaining in list are unchecked elements.
The outer loop runs while at least 2 elements remain in list. If only a single element remains in list, that element is the largest. The final element is handled immediately before the return statement.
Many students struggle with compareTo. The result of compareTo should always be compared against 0. Pretend the comparison operator replaces the method call.
if(list.get(j).compareTo(list.get(minIndex)) < 0)
means
if(list.get(j) < list.get(minIndex))
See compareTo on the AP CS A Exam.
The ArrayList method remove is not void. The remove method returns the element that was just removed from the list. It is very common, and acceptable, to treat the remove method as if it was void by ignoring the return value. The statement sortedList.add(list.remove(0)); does not ignore the return value. It adds the element that was removed from list to sortedList. The ArrayList method set is also not void. The set method returns the element that was just replaced by a new value. AP CS A Exam questions sometimes make use of the return values from remove and set, which sometimes confuses students.