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 unsorted element in that position.

For example:

Selection sort proceeds like this:

1. Find the smallest value (1) and swaps it with the value at index 0, resulting in 1 3 9 7 5.
2. Find the smallest remaining value, starting at index 1, which is 3. This is already in the correct position, so it swaps with itself and there is no change. The result is 1 3 9 7 5.
3. Find the smallest remaining value, starting at index 2, which is 5, and swaps it with the value at index 2, resulting in 1 3 5 7 9.
4. Find the smallest remaining value, starting at index 3, which is 7. This is already in the correct position, so it swaps with itself and there is no change. The result is 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.