Selection Sort

Selection sort traverses the array to find the smallest (or largest) element, then swaps it with the element at the beginning of the array. Then, it starts again for the remaining part of the array: it searches for the smallest among the not yet sorted elements, and swaps it with the first free position, and so on until everything is sorted.

In summary:

• At each step, we select the smallest remaining element,
• We place it in its correct position,
• Then we continue with the rest of the array.