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

### Step 1

The partition starts before the first element. The statements above are both true (since there is nothing to the left of the `|`

).

`[ | 71 86 79 36 78 35 75 86 24 11]`

### Step 2

The algorithm finds the smallest value in the unchecked part of the array (11). The algorithm swaps the smallest value in the unchecked part with the first value in the unchecked part (71).

The array is now

`[11 | 86 79 36 78 35 75 86 24 71]`

The statements above are true following the first pass through the array.

### Step 3

The algorithm finds the smallest value in the unchecked part (24). It swaps the 24 with the first value in the unchecked part (86).

The array is now

`[11 24 | 79 36 78 35 75 86 86 71]`

The statements above are true following the second pass through the array.

### Remaining steps

If we repeat this process, we end up with a sorted array. The remaining sequence of steps is shown below. Note that selection sort does NOT copy the array. The array is copied here only to show the progression.

```
[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 statements above are true following each pass through the array.

We stop the process before the last element. If every element except the last is in its final position, the last element must also be in its final position. (This array happens to contain the value 86 twice, but that makes no difference.)

## 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:

`findIndexOfMin`

finds the index of the minimum in the unchecked part of the array. It does this recursively.`swap`

is self explanatory.`sort(int[], int)`

is the private recursive helper method for`sort(int[])`

.`sort(int[], int)`

recursively sorts the part of the array starting at its parameter`startIndex`

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