Selection Sort
Description
♦ Selection sort works by finding the smallest element in the array and then swapping it with the value in the first position, then finding the second
smallest element and swapping it with the element in the second position, etc (or vice versa if finding largest element...)
♦ This clearly takes two loops, one to keep track of placed items, and one to keep track of the comparisons.
♦ Since each loop has N (number of elements in it), a multiplication results in a component of N2 - smaller components are ignored since, for large N,
the order is drive by the one with the highest exponent.
♦ The order of selection sort is N2 This is referred to as O(N2 )
The Algorithm
void selectionSort(int[] list)
{
int min, temp;
for (int outer = 0; outer < list.length - 1; outer++)
{
min = outer;
for (int inner = outer + 1; inner < list.length; inner++)
{
if (list[inner] < list[min])
{
min = inner; // a new smallest item is found
}
}
//swap list[outer] & list[min]
temp = list[outer];
list[outer] = list[min];
list[min] = temp;
}
}