Selection Sort

Imagine a teacher arranging exam papers by score from lowest to highest. Instead of swapping neighbors over and over, the teacher looks through the unsorted pile, finds the lowest-scoring paper, and places it first. Then the teacher repeats the process for the remaining pile.

That is the core idea of selection sort: each pass selects the smallest remaining element and places it in its final position.

Selection sort is a comparison-based sorting algorithm that repeatedly finds the minimum element from the unsorted portion of the collection and swaps it with the first unsorted position.

How selection sort works

• Start at index i = 0. Assume the current position holds the minimum element.

• Scan indices i + 1 to the end, updating the minimum index whenever a smaller value is found.

• After the scan finishes, swap the minimum element into position i.

• Increment i and repeat the same process for the remaining unsorted portion.

Interactive animation

In this visualizer, yellow marks the current minimum, purple marks the value currently being scanned, red shows the swap, and green shows positions that are already fixed.

Algorithm

The algorithm below shows how selection sort finds and places the minimum element at each step.

1. Start from the beginning of the list.

2. For each position i from 0 to n - 1:

   1. Assume the current position contains the smallest element.

   2. Keep track of its index as the minimum index.

   3. Scan the remaining portion of the list (from i + 1 to n - 1):

      1. Compare each element with the current minimum.

      2. If a smaller element is found:

         1. Update the minimum index.

   4. After scanning all remaining elements:

      1. Swap the element at the current position with the element at the minimum index.

Step-by-step trace

Let’s trace selection sort on $[29,10,$ ...