# Selection Sort

## Overview of selection sort

• Selection sort searches through the unsorted values to find the next lowest/highest value to append to the sorted values.
• Selection sort is one of the simple exchange sorts using two nested loops requiring O(n2) time.
• Programmers are expected to understand basic sorts, but it is much better (more reliable, faster to program, faster execution time) to use the Java library sorts: `java.util.Arrays.sort(...)` or `java.util.Collections.sort(...)`.

## Selection sort description

The selection sort algorithm sorts an array into ascending (or descending) order by dividing an array into two sections: a sorted section at the beginning and an unsorted portion after that. Initially the sorted portion has nothing in it, and the whole array is the unsorted portion.

1. Find the lowest value in the unsorted portion.
2. remove it from the unsorted portion and add it to the sorted portion.
3. Go back to step 1.

To avoid the inefficiencies of removing and inserting array elements, a clever shortcut is used to simply exchange the smallest value with the first unsorted element and move the boundary of the unsorted up one place.

This is easy to program, but isn't the fastest sort. The time selection sort requires goes up as the square of the number of data elements (O(n2), however if you don't have much data, eg fewer than 100 elements, selection sort is perfectly acceptable.

## Simple selection sort in Java

Remember the index of the smallest element that it finds in each pass of the inner loop over the unsorted values. After the smallest unsorted value is found, add it to the end of the sorted values by exchanging it with the first unsorted value (which then becomes the last sorted value).

```public static void selectionSort1(int[] x) {
//... i is the first element after the sorted portion of the array.
for (int i = 0; i < x.length-1; i++) {
int minIndex = i;      // Index of smallest unsorted value.  Assume first.
//... Look at the remaining unsorted for something smaller.
for (int j = i+1; j < x.length; j++) {
if (x[minIndex] > x[j]) {
minIndex = j;  // Remember index of new minimum
}
}
//... Move smallest unsorted to front by exchanging it.
int temp = x[i];
x[i] = x[minIndex];
x[minIndex] = temp;
}
}```

## Common variation of selection sort.

In the previous selection sort code, an exchange is always made, even if the first unsorted element was the smallest, which would cause an exchange with itself. There's no harm in exchanging an element with itself, but it's a waste of time. The 'if' is certainly slightly faster than the exchange, so this will be faster when the file is already sorted, but it's doubtful that it's worth the 'if'. Remember, you probably should use the faster library sort anyway.

```public static void selectionSort2(int[] x) {
for (int i = 0; i < x.length-1; i++) {
int minIndex = i;      // Index of smallest unsorted value.
for (int j = i+1; j < x.length; j++) {
if (x[minIndex] > x[j]) {
minIndex = j;  // Remember index of new minimum
}
}
if (minIndex != i) {
//... Move smallest unsorted to front by exchanging it.
int temp = x[i];
x[i] = x[minIndex];
x[minIndex] = temp;
}
}
}```

Extra if. It's a minor point, but the first example will sometimes run faster than the second. Why? If the data is already sorted initially, no exchanges will be made, so all if conditions will be false and therefore useless overhead. The second algorithm executes more if's and would therefore be slower. Data that is already sorted is more common that you might think at first.

## Variations

• Add extra parameters to indicate the subscript range to sort. Use the same header as the Java library sort:
`static void sort(int[] a, int fromIndex, int toIndex)`

fromIndex is the index of the first element of the array to sort, and toIndex is the index of the element AFTER the last one to sort (a common way to denote the upper bound).
• Add an extra boolean parameter to indicate whether the sort should be ascending or descending.
• Change it to sort strings.