Selection Sort Explained Simply – DSA Blog 8

The Real-Life Analogy First

Imagine you're a teacher who just received 30 answer sheets from students, all shuffled randomly. You need to hand them back in roll number order.

What's the most natural thing you do?

You scan all 30 sheets, find Roll No. 1, pull it out and place it first. Then scan the remaining 29, find Roll No. 2, place it second. And so on.

That's Selection Sort. Every pass, you scan everything remaining and select the minimum to place it correctly.

What is Selection Sort?

Selection Sort divides the array into two regions at every step:

• Sorted region — on the left, grows by one element each pass
• Unsorted region — on the right, shrinks by one each pass

Each pass: scan the unsorted region, find the minimum, swap it to the front of unsorted. Repeat until done.

Step-by-Step Walkthrough

Let's sort [64, 25, 12, 22, 11] from scratch. Click through each pass:

Key observation: with 5 elements, we made exactly 4 passes and only 2 actual swaps. That's Selection Sort's superpower — it minimises writes.

The JavaScript Code — Line by Line

function selectionSort(arr) {
  let n = arr.length;

  for (let i = 0; i < n - 1; i++) {      // i = boundary of sorted region
    let minIndex = i;                      // assume current pos is minimum

    for (let j = i + 1; j < n; j++) {    // scan unsorted region
      if (arr[j] < arr[minIndex]) {
        minIndex = j;                      // found a new minimum
      }
    }

    if (minIndex !== i) {                  // only swap if necessary
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

console.log(selectionSort([64, 25, 12, 22, 11]));
// Output: [11, 12, 22, 25, 64]

Breaking it down:

• i = the left boundary — everything to its left is already sorted
• minIndex starts as i — we assume it's the smallest until proven otherwise
• Inner j loop scans right of i, updating minIndex whenever it finds something smaller
• We only swap if minIndex !== i — no point swapping an element with itself
• ES6 destructuring [a,b]=[b,a] makes the swap clean — no temp variable needed

Time & Space Complexity — Why It's Always O(n²)

Unlike Bubble Sort which can detect a sorted array and stop early, Selection Sort has no early-exit mechanism. Even if the array is perfectly sorted, it still scans every element every pass.

Best = Average = Worst case: O(n²)

• For n=5: inner loop runs 4+3+2+1 = 10 comparisons
• For n=100: 99+98+...+1 = 4,950 comparisons
• For n=1,000: ~500,000 comparisons

Double the input → four times the work. That's what quadratic growth means.

Space complexity: O(1) — no extra arrays, no recursion stack. Just one swap variable. This is called in-place sorting.

Selection Sort vs Bubble Sort — The Clear Answer

This comparison comes up in almost every DSA interview. Here's the definitive answer:

Both are O(n²). But Selection Sort makes far fewer memory writes.

• Bubble Sort can swap up to O(n²) times — every out-of-order adjacent pair triggers a swap
• Selection Sort makes at most n−1 swaps total — exactly one per pass
• This matters when writing to memory is expensive: SSD writes, EEPROM, flash storage all have limited write cycles. Fewer swaps = longer hardware life

However, Bubble Sort is stable; Selection Sort is not. If two students both scored 85, Bubble Sort keeps their original order — Selection Sort may flip them. When sorting records with multiple fields, stability matters.

When Would You Actually Use Selection Sort?

Practically speaking, you'd rarely use it in production. But it genuinely shines in specific cases:

✅ Use it when:

• Teaching or learning — it's the most intuitive sorting algorithm to understand
• Working with very small datasets where O(n²) doesn't matter
• Writing to slow or limited-write memory (EEPROM, flash) — minimum swaps matter
• Implementing Heap Sort — which is Selection Sort made efficient by using a heap to find minimums in O(log n) instead of O(n)

❌ Avoid it when:

• Dataset is large — use Merge Sort O(n log n) or Quick Sort instead
• You need stable sort — use Insertion Sort or Merge Sort
• Data is nearly sorted — Insertion Sort handles that in near O(n)

Common Interview Questions — With Answers

Q: What is the time complexity of Selection Sort in all cases?

A: O(n²) in all cases — best, average, and worst. It always makes the same number of comparisons regardless of input order.

Q: Is Selection Sort stable?

A: No. It can change the relative order of equal elements when performing swaps.

Q: How many swaps does Selection Sort make at most?

A: At most n−1 swaps — one per pass. This is its key advantage over Bubble Sort.

Q: What's the space complexity?

A: O(1) — in-place sorting, no extra memory needed beyond a few variables.

Q: Which is better — Selection Sort or Bubble Sort?

A: Selection Sort when swaps are expensive. Bubble Sort when stability is needed or data may already be sorted (it detects that and exits early).

Q: Where is Selection Sort used in real algorithms?

A: Heap Sort is a direct evolution of Selection Sort — it uses a max-heap to efficiently find the maximum element each pass, bringing time down to O(n log n).

Quick Practice — Try It Yourself

Sort this array manually using Selection Sort:

[29, 10, 14, 37, 13]

Trace through each pass: what is the minimum? What gets swapped? How many total swaps?

Answer: Pass 1→swap 10↔29. Pass 2→swap 13↔14. Pass 3&4→no swaps needed. Total: 2 swaps. Result: [10, 13, 14, 29, 37]

The One-Sentence Mental Model

Selection Sort = "Scan everything, pick the smallest, lock it in. Repeat."

• Bubble Sort = "Swap neighbours until big ones bubble to the end"
• Selection Sort = "Select the minimum, place it precisely"
• Insertion Sort = "Pick one card at a time, slide it into the right spot in your hand"

Our DSA Roadmap

Every blog in this series builds on the previous one. Here's where you are:

What's Next?

Blog 9: Insertion Sort Explained Simply

Insertion Sort works like sorting playing cards in your hand — you pick one card at a time and slide it into the correct position among the already-sorted cards. It's O(n²) in the worst case like Selection Sort, but has a superpower: it runs in O(n) time on nearly-sorted arrays. See you in Blog 9! 🚀

Continue your DSA journey: Browse all DSA blogs on Bitveen