Selection Sort: Algorithm
You'll learn how selection sort works by repeatedly finding the smallest element and moving it to the front of the unsorted portion.
The Core Idea
Imagine you have a row of books in random order and want to arrange them by height. Selection sort works like this: scan all the books, find the shortest one, and place it first. Then scan the remaining books, find the shortest among those, and place it second. Repeat until done.
Selection sort divides your array into two portions:
- Sorted portion: the leftmost part, grows one element at a time
- Unsorted portion: everything to the right, shrinks as we go
How It Works
The algorithm follows these steps:
- Start with the entire array unsorted
- Find the minimum element in the unsorted portion
- Swap it with the first element of the unsorted portion
- Move the boundary between sorted and unsorted one position right
- Repeat until only one element remains
Step-by-Step Example
Consider the array: [64, 25, 12, 22, 11]
Pass 1: Find minimum (11), swap with position 0
→ [11, 25, 12, 22, 64]
Pass 2: Find minimum in remaining (12), swap with position 1
→ [11, 12, 25, 22, 64]
Pass 3: Find minimum in remaining (22), swap with position 2
→ [11, 12, 22, 25, 64]
Pass 4: Find minimum in remaining (25), already in place
→ [11, 12, 22, 25, 64]
Done! Notice how the sorted portion (underlined conceptually) grows left-to-right while we keep selecting the smallest from what remains.
Key Takeaway: Selection sort builds the sorted array by repeatedly selecting the minimum element from the unsorted portion and placing it at the end of the sorted portion, requiring n-1 passes through the data.