How Selection Sort Works

Selection sort uses nested loops to find the minimum element and swap it into place.

The Algorithm

Here’s the pseudocode:

for i from 0 to n-1
  minIndex = i
  for j from i+1 to n
    if array[j] < array[minIndex]
      minIndex = j
  swap(array[i], array[minIndex])

Step-by-Step Example

Let’s sort [64, 25, 12, 22, 11]:

Pass 1 (i=0):

• Find minimum in [64, 25, 12, 22, 11]
• Minimum is 11 at index 4
• Swap 64 and 11 → [11, 25, 12, 22, 64]
• Sorted portion: [11]

Pass 2 (i=1):

• Find minimum in [25, 12, 22, 64]
• Minimum is 12 at index 2
• Swap 25 and 12 → [11, 12, 25, 22, 64]
• Sorted portion: [11, 12]

Pass 3 (i=2):

• Find minimum in [25, 22, 64]
• Minimum is 22 at index 3
• Swap 25 and 22 → [11, 12, 22, 25, 64]
• Sorted portion: [11, 12, 22]

Pass 4 (i=3):

• Find minimum in [25, 64]
• Minimum is 25 at index 3 (already in place)
• No swap needed → [11, 12, 22, 25, 64]
• Array is sorted!

Visual Representation

Key Points

1. Outer loop: Runs n-1 times

   • After each iteration, one more element is in place

2. Inner loop: Finds minimum in unsorted portion

   • Starts from i+1 (unsorted portion)

3. Swap: Places minimum at correct position

   • Swaps with first element of unsorted portion

Why n-1 Passes?

After n-1 passes, n-1 elements are in their correct positions. The last element is automatically in the right place, so we don’t need a final pass.

Comparison with Bubble Sort

Selection sort makes fewer swaps but always does the same number of comparisons.

What’s Next?

Now that you understand how it works, let’s see it in action with an interactive visualization.