CodeWithYash

Foundation · Module 4 · Lesson 2

Selection Sort

Select the next minimum and grow a sorted prefix.

15–25 min readLesson 20 of 123 Interactive Lab
Jump to interactive visualizer

Lesson 20 of 123

1d streak

Interactive Visualization

Trace the algorithm state by state

Change the inputs, run an operation, and connect each visible state change to the explanation below.

Step-through visualizer

Selection Sort

Follow the state transition, then use the controls to test your prediction.

Purple: Current Minimum candidateOrange: Under comparisonGreen: Locked in Sorted Prefix
25
0
12
1
38
2
7
3
19
4
2
5
startBegin with the entire array as the unsorted partition.
Step 1 / 39

Theory lesson · Step-by-step

Understand Selection Sort

Select the next minimum and grow a sorted prefix.

Worked approach

Trace the reasoning step by step

  1. 1For each position i, scan the unsorted suffix.
  2. 2Find its minimum index.
  3. 3Swap that minimum into position i.

Concrete example

Sort [3, 1, 2] by selecting minima.

  1. 1Minimum of all values is 1; swap with index 0.
  2. 2Minimum of [3,2] is 2; swap.

The sorted result is [1, 2, 3].

What must remain true (Loop Invariant)

The prefix before i is sorted and contains the i smallest values.

Cost Model

Complexity & Trade-offs

Sort
O(n²)
O(1)
Include stability and input shape when comparing sorts.

When to use it

  • Creating order before searching, grouping, deduplicating, or scanning.
  • Selecting records using stability, memory, and input-shape constraints.
  • Turning pairwise decisions into monotonic scans.

Common mistakes

  • Comparing time alone while ignoring stability and auxiliary memory.
  • Breaking duplicate order when stability is required.
  • Quoting average performance without worst-case behavior.

Practice prompts

  • Reproduce the worked Selection Sort example without looking at the trace.
  • Change one input condition and explain whether the Selection Sort invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.