Selection Sort

What Is Selection Sort?

Selection sort divides the array into two regions: a sorted prefix on the left and an unsorted suffix on the right. In each pass, it selects the minimum element from the unsorted region and swaps it to the front of that region — growing the sorted prefix by one element.

Array: [64, 25, 12, 22, 11]

Pass 1: unsorted=[64,25,12,22,11]  min=11 at index 4  → swap with index 0
        [11, 25, 12, 22, 64]   sorted=[11] | unsorted=[25,12,22,64]

Pass 2: unsorted=[25,12,22,64]     min=12 at index 2  → swap with index 1
        [11, 12, 25, 22, 64]   sorted=[11,12] | unsorted=[25,22,64]

Pass 3: unsorted=[25,22,64]        min=22 at index 3  → swap with index 2
        [11, 12, 22, 25, 64]   sorted=[11,12,22] | unsorted=[25,64]

Pass 4: unsorted=[25,64]           min=25 at index 3  → already in place (no swap)
        [11, 12, 22, 25, 64]   sorted=[11,12,22,25] | unsorted=[64]

Array fully sorted after n-1 = 4 passes.
Total swaps: 3  (pass 4 placed the minimum without swapping — it was already there)

The key difference from bubble sort: selection sort makes at most one swap per pass, no matter how disordered the array is.

Basic Selection Sort

Output:
[11, 12, 22, 25, 64]
[10, 13, 14, 29, 37]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

Complete Dry Run: [64, 25, 12, 22, 11]

Tracing every pass — showing the full unsorted-region scan and swap decision:

arr = [64, 25, 12, 22, 11]   n=5

PASS 1 (i=0): scan arr[1..4] for minimum
  minIdx=0 (val=64)
  j=1: arr[1]=25 < 64 → minIdx=1
  j=2: arr[2]=12 < 25 → minIdx=2
  j=3: arr[3]=22 > 12 → no
  j=4: arr[4]=11 < 12 → minIdx=4
  → minimum is 11 at index 4 ≠ 0 → SWAP arr[0] and arr[4]
  [11, 25, 12, 22, 64]
   ↑ sorted

PASS 2 (i=1): scan arr[2..4] for minimum
  minIdx=1 (val=25)
  j=2: arr[2]=12 < 25 → minIdx=2
  j=3: arr[3]=22 > 12 → no
  j=4: arr[4]=64 > 12 → no
  → minimum is 12 at index 2 ≠ 1 → SWAP arr[1] and arr[2]
  [11, 12, 25, 22, 64]
   ↑---↑ sorted

PASS 3 (i=2): scan arr[3..4] for minimum
  minIdx=2 (val=25)
  j=3: arr[3]=22 < 25 → minIdx=3
  j=4: arr[4]=64 > 22 → no
  → minimum is 22 at index 3 ≠ 2 → SWAP arr[2] and arr[3]
  [11, 12, 22, 25, 64]
   ↑---↑---↑ sorted

PASS 4 (i=3): scan arr[4..4] for minimum
  minIdx=3 (val=25)
  j=4: arr[4]=64 > 25 → no
  → minimum is 25 at index 3 = 3 → NO SWAP (already in place)
  [11, 12, 22, 25, 64]
   ↑---↑---↑---↑ sorted

Fully sorted: [11, 12, 22, 25, 64] ✓
Total comparisons: 4+3+2+1 = 10
Total swaps:       3  (pass 4 required no swap)

Why Selection Sort Is Not Adaptive

Even if the input is already sorted, selection sort always
scans the entire unsorted region to confirm the minimum.

Already sorted: [1, 2, 3, 4, 5]

PASS 1 (i=0): scan j=1..4 — confirms 1 is minimum — no swap
PASS 2 (i=1): scan j=2..4 — confirms 2 is minimum — no swap
PASS 3 (i=2): scan j=3..4 — confirms 3 is minimum — no swap
PASS 4 (i=3): scan j=4..4 — confirms 4 is minimum — no swap

Total comparisons: 4+3+2+1 = 10  ← same as worst case
Total swaps:       0

The algorithm cannot detect that the array is sorted
because it has no mechanism to skip the scan.
This is why selection sort is NOT adaptive —
best case = average case = worst case = O(n²).

Contrast with bubble sort (early exit):
  Already sorted input: 1 pass, 4 comparisons, 0 swaps → O(n).

Why Selection Sort Is Unstable

Selection sort swaps the minimum element directly to position i. This long-distance swap can jump over equal elements, breaking their original relative order.

Input: [(B,3), (A,3), (C,1)]   sort by number (letter is tiebreaker)
       key=number, want ascending by number

PASS 1 (i=0): scan for minimum by number
  minIdx starts at 0 (B,3)
  j=1: (A,3) — 3 < 3? No → minIdx stays 0
  j=2: (C,1) — 1 < 3? Yes → minIdx=2
  → minimum (C,1) at index 2 ≠ 0 → SWAP index 0 and index 2

  Before swap: [(B,3), (A,3), (C,1)]
  After swap:  [(C,1), (A,3), (B,3)]
                               ↑  ↑
               B and A REVERSED — original order was B before A (both have value 3)

Result: [(C,1), (A,3), (B,3)]
  (A,3) and (B,3) are now in different relative order than input → UNSTABLE

Why: swapping the minimum (C,1) with (B,3) moved (B,3) to the back,
     past (A,3), without any logical need to change their relative order.
     Selection sort's non-adjacent swap is the root cause of instability.

Optimisation: Double-Ended Selection Sort

Select both the minimum AND maximum in each pass, placing both in their final positions simultaneously. This halves the number of passes.

Output:
[3, 11, 12, 22, 25, 64, 90]
[1, 2, 3, 4, 5, 7, 8]

Dry Run: Double Selection Sort [64, 25, 12, 22, 11]

lo=0, hi=4

ROUND 1: scan arr[0..4]
  min=11 at index 4,  max=64 at index 0

  Place min at lo=0:  swap arr[0] and arr[4]
    → [11, 25, 12, 22, 64]
    maxIdx was 0, moved to 4 after swap → maxIdx=4

  Place max at hi=4:  maxIdx=4 == hi=4 → no swap needed
    → [11, 25, 12, 22, 64]

  lo=1, hi=3

ROUND 2: scan arr[1..3]
  min=12 at index 2,  max=25 at index 1

  Place min at lo=1:  swap arr[1] and arr[2]
    → [11, 12, 25, 22, 64]
    maxIdx was 1, moved to 2 after swap → maxIdx=2

  Place max at hi=3:  swap arr[3] and arr[2]
    → [11, 12, 22, 25, 64]

  lo=2, hi=2 → lo < hi is false → DONE

Result: [11, 12, 22, 25, 64] ✓
Passes: 2 instead of 4 — half the passes!

Critical edge case: when max was at lo before the min swap,
  maxIdx must be updated to minIdx after the swap.
  Forgetting this causes the wrong element to be placed at hi.

Counting Comparisons and Swaps

SELECTION SORT — n=5 array:

comparisons per pass:
  Pass 1 (i=0): 4  (scan j=1..4)
  Pass 2 (i=1): 3  (scan j=2..4)
  Pass 3 (i=2): 2  (scan j=3..4)
  Pass 4 (i=3): 1  (scan j=4..4)

Total comparisons = 4+3+2+1 = n(n-1)/2 = 10  (same in ALL cases)

Max swaps = n-1 = 4  (one per pass, only if minIdx ≠ i)
Min swaps = 0        (already sorted — no swap needed in any pass)

Contrast with bubble sort (worst case):
  Comparisons: 10  (same)
  Swaps:       10  (every comparison triggers a swap for reverse-sorted)

Selection sort's advantage: at most n-1 swaps regardless of input.
This matters when writes are expensive (flash storage, remote writes).

Selection Sort vs Bubble Sort — Side by Side

Property            Selection Sort        Bubble Sort (optimised)
──────────────────────────────────────────────────────────────────
Best case           O(n²)                 O(n)   ← bubble wins
Average case        O(n²)                 O(n²)
Worst case          O(n²)                 O(n²)
Comparisons         n(n-1)/2 always       n(n-1)/2 worst; n-1 best
Swaps               ≤ n-1 always          ≤ n(n-1)/2
Stable              ✗ No                  ✓ Yes   ← bubble wins
Adaptive            ✗ No                  ✓ Yes   ← bubble wins
In-place            ✓ O(1)                ✓ O(1)
Write-minimising    ✓ Yes (≤ n-1 writes)  ✗ No    ← selection wins

Selection sort's sole performance advantage over bubble sort: it guarantees the minimum number of write (swap) operations. In systems where writing is far more expensive than reading (flash memory, NVRAM, network I/O), selection sort's ≤ n-1 swaps make it preferable.

Complexity Summary

Stable: No — long-distance swaps break equal element order. Adaptive: No — always n(n-1)/2 comparisons regardless of input. In-place: Yes — O(1) extra space.

Common Mistakes

Not updating maxIdx when the max element was displaced by the min swap in double selection sort. This is the most critical bug in the double-ended variant. If the maximum is initially at lo and you swap the minimum to lo, the maximum moves to minIdx. If you then try to swap arr[maxIdx] (still pointing to lo) to hi, you place the wrong element. Always check: if (maxIdx == lo) maxIdx = minIdx after the first swap.

Swapping even when minIdx == i. This is harmless but wasteful — swapping an element with itself. The if (minIdx != i) guard avoids a no-op swap. Some implementations omit this guard and always swap, which produces the correct output but does unnecessary writes.

Starting the inner loop at j = i instead of j = i + 1. Starting at i means minIdx might never move from i even when a smaller element exists elsewhere. Always start the scan at j = i + 1 since arr[i] is already the tentative minimum.

Using <= in the outer loop: i <= n - 1 instead of i < n - 1. The last pass (i = n-1) would scan an empty range and swap arr[n-1] with itself — a no-op. The outer loop should run only n-1 times: i < n - 1 or equivalently i = 0; i < n - 1.

Interview Questions

Q: Why is selection sort O(n²) even for already-sorted input?

Selection sort must scan the entire unsorted region to confirm the minimum — it has no way to know the minimum is already at arr[i] without checking every other element. Even when no swaps occur (already-sorted input), the comparison count is always n(n-1)/2 = O(n²). Unlike bubble sort with early exit, selection sort is not adaptive — it cannot skip work based on the input's current state.

Q: Why is selection sort considered when write operations are expensive?

Selection sort makes at most n-1 swaps — one per pass, and only when the minimum is not already in place. Bubble sort can make O(n²) swaps in the worst case (every comparison triggers a swap for reverse-sorted input). When writes are much more expensive than reads — flash memory, NVRAM, remote data updates — selection sort's guaranteed write count of ≤ n-1 makes it preferable despite identical comparison counts.

Q: Prove that selection sort is not stable with a concrete example.

Take [(B,3), (A,3), (C,1)] sorted by number. Pass 1 finds the minimum (C,1) at index 2 and swaps it with (B,3) at index 0. Result: [(C,1), (A,3), (B,3)]. The elements (B,3) and (A,3) have swapped their relative positions — B was before A in the input but is after A in the output. The long-distance swap moved B past A without justification.

FAQs

Can selection sort be made stable?

Yes — instead of swapping the minimum to position i, insert it by shifting all elements between i and minIdx one position to the right (like insertion sort). This preserves relative order. However, this makes each pass O(n) time with O(n) moves instead of O(1) moves — the total becomes O(n²) moves, the same as insertion sort. At that point you have effectively implemented insertion sort, which is better in every other way.

Does selection sort work on linked lists?

Yes — find the minimum by traversal (O(n)), then swap the values (O(1) if swapping values, O(n) if relinking nodes). For linked lists, selection sort is simpler to implement than for arrays since there is no need to track indices. However, insertion sort is more efficient for linked lists because inserting at the correct position costs O(1) pointer relinking once the position is found.

How does double selection sort compare to standard selection sort?

Double selection sort halves the number of passes (n/2 instead of n-1) but still scans the same elements in each pass. Total comparisons remain n(n-1)/2. Total swaps become at most n instead of n-1 (two swaps per round instead of one). The actual speedup is marginal — it is the same O(n²) with roughly the same constant. The code is more complex (the displaced maxIdx bug is easy to miss). Not useful in production, but occasionally asked in interviews.

Summary

Selection sort builds a sorted prefix by repeatedly selecting the minimum from the unsorted suffix and swapping it to the front of that suffix.

Key properties:

• ›One scan per pass — always reads every unsorted element to find the minimum
• ›At most one swap per pass — minimum writes among all simple O(n²) sorts
• ›Not adaptive — O(n²) comparisons regardless of input order; early exit cannot be added
• ›Not stable — long-distance swaps can reverse equal elements
• ›In-place — O(1) extra space

Complexity: O(n²) comparisons in all cases; at most n-1 swaps; O(1) space.

Double-ended variant: find min and max simultaneously; halves passes but not total comparisons; critical to update maxIdx if max was displaced by the min swap.

Selection sort vs bubble sort:

• ›Bubble sort is better: O(n) best case (early exit), stable, adaptive
• ›Selection sort is better: ≤ n-1 swaps always (minimises writes)

In the next topic, you will explore Insertion Sort — the adaptive O(n²) sort that is genuinely fast for nearly-sorted input, maintains a sorted prefix by inserting each new element in the right place, and is stable.