Course contentsShow
← Computer Science
Lesson 744 of 2,87218. Sorting AlgorithmsFree lesson

Selection Sort: Algorithm

Learning selection sort: repeatedly find the minimum element and place it at the beginning of unsorted portion.

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:

  1. Start with the entire array unsorted
  2. Find the minimum element in the unsorted portion
  3. Swap it with the first element of the unsorted portion
  4. Move the boundary between sorted and unsorted one position right
  5. 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.