# Java Notes

# 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(n
^{2}) 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.

- Find the lowest value in the unsorted portion.
- remove it from the unsorted portion and add it to the sorted portion.
- 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(n^{2}), 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.