Selection Sort

Select the Minimum, Swap to Front

1:00

How selection sort works — repeatedly selecting the minimum of the unsorted suffix and swapping it to the front — and why it trades O(n²) comparisons for a minimal number of writes.

By the end, you can

Trace selection sort step by step on a small array, identifying the minimum found and the swap made on each pass.
State the sorted-prefix invariant and explain why each swapped element is permanently in place.
Count the exact number of comparisons and swaps for an array of size n.
Explain why selection sort is not adaptive and give its time complexity for best, average, and worst case (all O(n²), since it always scans the full unsorted region).
Explain why selection sort makes fewer writes than bubble sort and when that matters.
Give a concrete example showing that selection sort is not stable, and explain the mechanism.
Name the scenarios where selection sort is a reasonable choice and when to prefer alternatives.

Up next in Searching & Sorting