Selction Sort

Selection sort repeatedly finds the smallest remaining element and places it in its correct position.

The algorithm divides the array into two parts:

a sorted portion at the beginning an unsorted portion containing the remaining elements

During each pass, it searches the unsorted portion for the smallest value and swaps it with the first unsorted element.

For example:

Selection sort proceeds like this:

1. Find the smallest value (1) and insert it at index 0, resulting in 1 7 3 9 5.
2. Find the smallest remaining value, starting at index 1, which is 3, and insert it at index 0, resulting in 1 3 7 9 5.
3. Find the smallest remaining value, starting at index 2, which is 5, and insert it at index 0, resulting in 1 3 5 7 9.
4. Find the smallest remaining value, starting at index 3, which is 7, and insert it at index 0, resulting in 1 3 5 7 9.
5. The last element is already in place at the end.

The final result is:

1 3 5 7 9

Unlike insertion sort, selection sort places one element into its final position during each pass through the array.