Selection sort

Maintain two parts of the array, sorted and unsorted parts. Starting with the sorted part being empty and the unsorted part being $A[0..N-1]$, repeatedly find the smallest integer in the unsorted part and swap it to the end of the sorted part.

A small example will explain the process quickly. In this example, the unsorted part is bold.

• Step $0$: $[6, 3, 5, 4, 1, 2]$
• Step $1$: find minimum in $A[0..5]$ and move to 0 -> $[1, 3, 5, 4, 6, 2]$.
• Step $2$: find minimum in $A[1..5]$ and move to 1 -> $[1, 2, 5, 4, 6, 3]$.
• Step $3$: find minimum in $A[2..5]$ and move to 2 -> $[1, 2, 3, 4, 6, 5]$.