Selection Sort

Selection sort repeatedly finds the minimum element and moves it to its correct position.

The idea: Divide the array into sorted (left) and unsorted (right) portions. Find the minimum in the unsorted portion. Swap it to the end of the sorted portion. Repeat.

Walkthrough for $[64, 25, 12, 22, 11]$:

$1.$ Find min ($11$), swap with first: $[11, 25, 12, 22, 64]$

$2.$ Find min in rest ($12$), swap: $[11, 12, 25, 22, 64]$

$3.$ Find min in rest ($22$), swap: $[11, 12, 22, 25, 64]$

$4.$ Find min in rest ($25$), already in place: $[11, 12, 22, 25, 64]$