Selection Sort Explained: Step-by-Step Trace, Complexity and Exam Traps

Learn the invariant behind Selection Sort, trace every pass, derive its exact comparison count, and avoid common stability and swap-count traps.

KnowledgeGate Team

Exam prep & CS education

Updated 18 Nov 20265 min read
Selection Sort Explained: Step-by-Step Trace, Complexity and Exam Traps

Selection sort seems simple, but exams rarely stop at its definition. They ask for the array after a named pass, exact comparison and exchange counts, and whether equal records retain their order. In the standard minimum-selection, swap-based version, each pass finds the minimum in the unsorted suffix and swaps it into the next position.

Selection sort fixes one final position in every pass

Before pass i, using zero-based indexing, A[0..i-1] is the sorted prefix containing the i smallest keys in their final positions. A[i..n-1] is the unsorted suffix. Find its minimum, store the index, and exchange it with A[i] only if the indices differ.

Code
for i = 0 to n - 2
    minIndex = i
    for j = i + 1 to n - 1
        if A[j] < A[minIndex]
            minIndex = j
    if minIndex != i
        swap A[i], A[minIndex]

After fixing the first n-1 positions, the final element is necessarily correct. Ascending selection sort chooses the minimum for the left boundary; the descending version chooses the maximum. Sorting sits inside the wider algorithms syllabus covered in GATE CS Exam Preparation.

The invariant also proves correctness. Before the first pass, the empty prefix is trivially final. Assume positions 0 through i-1 contain the i smallest keys in order. The minimum of the remaining suffix is therefore the next smallest key; swapping it into A[i] extends the final prefix without disturbing earlier positions. When i reaches n-2, only one suffix value remains, so the whole array is sorted. The suffix may still be in any order during an earlier pass, and nearly sorted input does not shorten its scan.

Selection sort worked example: trace all four passes

Take A=[29,10,14,37,13]. Keep values and indices distinct: in pass 2, the minimum is value 13 at current index 4.

Pass

Unsorted suffix

Selected minimum

Swap

Array after pass

Comparisons

1

[29,10,14,37,13]

10, index 1

29 with 10

[10,29,14,37,13]

4

2

[29,14,37,13]

13, index 4

29 with 13

[10,13,14,37,29]

3

3

[14,37,29]

14, index 2

None

[10,13,14,37,29]

2

4

[37,29]

29, index 4

37 with 29

[10,13,14,29,37]

1

The totals are 4+3+2+1=10 key comparisons and 3 actual exchanges because the pass-3 self-swap is skipped. After pass k, the first k cells are final, not merely sorted relative to one another.

Selection sort trace of [29,10,14,37,13] across four passes, showing each selected minimum, the swaps made and the comparison counts.

Selection sort complexity comes from a fixed comparison sum

Successive suffix scans make n-1,n-2,...,1 comparisons, so

(n-1)+(n-2)+...+1 = n(n-1)/2.

For n=5, this is 5x4/2=10; for n=100, it is 100x99/2=4,950. Even sorted input needs every scan, so best, average and worst time are Theta(n^2). Selection sort is non-adaptive, in-place and uses Theta(1) auxiliary space.

Comparisons are not exchanges. [1,2,3,4,5] needs 10 comparisons and 0 exchanges. [2,3,4,5,1] also needs 10 comparisons but exactly 4 exchanges. Conditional-swap selection sort makes at most n-1 exchanges. If pseudocode performs an unconditional self-swap, the question's convention changes the reported count.

Count conventions must come from the pseudocode. Key comparisons count evaluations of A[j] < A[minIndex]; loop-bound checks and the minIndex != i test are not key comparisons. An exchange may be reported as one swap or as three assignments through a temporary variable. The five-element trace therefore has 10 key comparisons, 3 swaps and, under the three-assignment convention, 9 data assignments caused by swaps. Naming the convention prevents a correct trace from receiving the wrong operation count.

Selection sort is in-place but not stable

Stability means equal-key records retain their original relative order. Consider [(4,A),(2,X),(4,B),(1,Y)], where record A precedes record B among the key-4 entries. Pass 1 swaps (1,Y) with (4,A), producing [(1,Y),(2,X),(4,B),(4,A)]. Now B precedes A, proving that standard swap-based selection sort is unstable.

Using < rather than <= to select the first minimum does not repair this example. The long-distance swap causes the reversal. A stable variant can remove the minimum and shift intervening records one position right, but that may require linear data movement per pass and loses the standard version's low-exchange advantage.

Stability counterexample where swapping the minimum (1,Y) with (4,A) leaves record B ahead of record A among the equal key-4 entries.

Selection sort versus bubble sort and insertion sort

Algorithm

Best time

Worst time

Stable

Adaptive

In-place

Data movement

Selection

Theta(n^2)

Theta(n^2)

No

No

Yes

At most n-1 exchanges

Optimised bubble

Theta(n)

Theta(n^2)

Yes

Yes

Yes

Up to quadratic swaps

Insertion

Theta(n)

Theta(n^2)

Yes

Yes

Yes

Up to quadratic shifts

Selection sort is rarely chosen for large inputs, but its at-most n-1 exchanges can matter when writes are substantially more expensive than reads. Insertion sort gains a linear best case from stopping within its sorted prefix; optimised bubble sort gains one from a no-swap pass. Selection sort gains neither because it scans every remaining suffix. For a cross-family decision by stability, space and growth rate, use Sorting Algorithms: Complexity, Stability, n log n Bound. Selection sort's decisive properties are its fixed comparison count, bounded exchanges and unstable long-distance swap.

Each pass makes a locally final choice and never revisits the fixed prefix. This connects to Greedy Algorithms: Strategy and Problems, although selection sort's exam identity remains its trace, comparison cost and stability.

Selection sort exam traps: trace, count and classify

Use these keyed checks:

  1. After k passes, the first k keys are final.

  2. Comparisons equal n(n-1)/2, not n-1.

  3. Actual exchanges are at most n-1, not quadratic.

  4. Standard selection sort is in-place but unstable.

  5. Descending order selects the maximum; it does not keep selecting the minimum while merely scanning backwards.

Trace A=[64,25,12,22,11]. Pass 1 selects 11 and gives [11,25,12,22,64]. Pass 2 selects 12 and gives [11,12,25,22,64]. The suffix need not be sorted, so [11,12,22,25,64] is not the state after two passes.

Before each practice trace, identify the loop variant, then record the suffix minimum, array state, cumulative key comparisons and actual exchanges after every pass. The GATE Test Series is an optional route for mixed timed practice.

Selection sort in the short version and the next step

  • Select the smallest suffix key.

  • Place it at the left boundary.

  • Repeat for n-1 passes.

  • Comparisons are always n(n-1)/2.

  • Exchanges are at most n-1.

  • The standard algorithm is in-place, non-adaptive and unstable.

Thus, [29,10,14,37,13] becomes [10,13,14,29,37] with 10 comparisons and 3 actual exchanges. Use GATE Guidance by Sanchit Sir if you want this topic placed inside a structured Algorithms sequence.

Self-test: What is the array after two passes, and how many total comparisons are required, when sorting [7,4,9,2,6,1]?

Answer: Pass 1 gives [1,4,9,2,6,7]; pass 2 gives [1,2,9,4,6,7]; total comparisons are 6x5/2=15.