PK

PKBytes

Explore tracks
Chapter 17: Elementary Sorting Algorithms
17.03Beginner / Intermediate5 topics12 min2 interactive animations

Selection sort

Selection sort grows a sorted prefix by repeatedly finding the minimum of the unsorted part and swapping it into place. It always makes n(n-1)/2 comparisons but at most n - 1 swaps.

Learning goals

  • Trace selection sort and its minimum search
  • Explain why it makes at most n - 1 swaps
  • Show with an example why it is not stable

Prerequisites

Finding a minimum in an arraySwapping
17.03.1

Find minimum

For each position i, scan arr[i..n-1] to find the index of the smallest value, then swap it into position i.

Invariant: after iteration i, arr[0..i] holds the i + 1 smallest values in sorted order, and they never move again.

Selection sort

Interactive · edit the input

Your input

Try

int[] arr · length 7

38
27
43
3
9
82
10
0123456
Being comparedCandidateMovedSorted
Setup

Grow a sorted prefix by repeatedly selecting the minimum of the unsorted part.

Step 1 / 48
Java
1public static void selectionSort(int[] arr) {
2    int n = arr.length;
3    for (int i = 0; i < n - 1; i++) {
4        int min = i;
5        for (int j = i + 1; j < n; j++) {
6            if (arr[j] < arr[min]) {
7                min = j;
8            }
9        }
10        if (min != i) {
11            int tmp = arr[i];
12            arr[i] = arr[min];
13            arr[min] = tmp;
14        }
15    }
16}

Live state

0 comparisons0 swaps

n

7

No condition evaluated on this step
Execution trace (dry run table)Show 48 steps
StepLineStateWhat happens
1L2n=7Grow a sorted prefix by repeatedly selecting the minimum of the unsorted part.
2L4i=0 min=0Assume arr[0] = 38 is the minimum of [0..6].
3L6i=0 min=0 j=1Smaller value found.
4L7i=0 min=1 j=1min = 1.
5L6i=0 min=1 j=2Not smaller.
6L6i=0 min=1 j=3Smaller value found.
7L7i=0 min=3 j=3min = 3.
8L6i=0 min=3 j=4Not smaller.
9L6i=0 min=3 j=5Not smaller.
10L6i=0 min=3 j=6Not smaller.
11L10i=0 min=3The minimum 3 belongs at index 0.
12L12i=0 min=3Swap arr[0] and arr[3]. A long-distance swap like this can reorder equal keys, so selection sort is not stable.
13L4i=1 min=1Assume arr[1] = 27 is the minimum of [1..6].
14L6i=1 min=1 j=2Not smaller.
15L6i=1 min=1 j=3Not smaller.
16L6i=1 min=1 j=4Smaller value found.
17L7i=1 min=4 j=4min = 4.
18L6i=1 min=4 j=5Not smaller.
19L6i=1 min=4 j=6Not smaller.
20L10i=1 min=4The minimum 9 belongs at index 1.
21L12i=1 min=4Swap arr[1] and arr[4]. A long-distance swap like this can reorder equal keys, so selection sort is not stable.
22L4i=2 min=2Assume arr[2] = 43 is the minimum of [2..6].
23L6i=2 min=2 j=3Smaller value found.
24L7i=2 min=3 j=3min = 3.
25L6i=2 min=3 j=4Smaller value found.
26L7i=2 min=4 j=4min = 4.
27L6i=2 min=4 j=5Not smaller.
28L6i=2 min=4 j=6Smaller value found.
29L7i=2 min=6 j=6min = 6.
30L10i=2 min=6The minimum 10 belongs at index 2.
31L12i=2 min=6Swap arr[2] and arr[6]. A long-distance swap like this can reorder equal keys, so selection sort is not stable.
32L4i=3 min=3Assume arr[3] = 38 is the minimum of [3..6].
33L6i=3 min=3 j=4Smaller value found.
34L7i=3 min=4 j=4min = 4.
35L6i=3 min=4 j=5Not smaller.
36L6i=3 min=4 j=6Not smaller.
37L10i=3 min=4The minimum 27 belongs at index 3.
38L12i=3 min=4Swap arr[3] and arr[4]. A long-distance swap like this can reorder equal keys, so selection sort is not stable.
39L4i=4 min=4Assume arr[4] = 38 is the minimum of [4..6].
40L6i=4 min=4 j=5Not smaller.
41L6i=4 min=4 j=6Not smaller.
42L10i=4 min=4arr[4] is already the minimum. No swap: selection sort does at most n - 1 swaps.
43L4i=5 min=5Assume arr[5] = 82 is the minimum of [5..6].
44L6i=5 min=5 j=6Smaller value found.
45L7i=5 min=6 j=6min = 6.
46L10i=5 min=6The minimum 43 belongs at index 5.
47L12i=5 min=6Swap arr[5] and arr[6]. A long-distance swap like this can reorder equal keys, so selection sort is not stable.
48L16Sorted with 21 comparisons, 5 swaps. The comparison count is always n(n-1)/2 = 21.
17.03.2

Minimum swaps

Selection sort performs at most one swap per position, so at most n - 1 swaps in total, no matter the input. Bubble and insertion sort can need up to n(n-1)/2 moves.

That makes it a reasonable choice when writes are far more expensive than reads, such as flash memory with limited write cycles. Cycle sort (17.05) goes further and writes each element at most once.

17.03.3

Instability

The long-distance swap can jump an element over an equal key. Example: [4a, 3, 4b, 1]. The first step swaps 4a with 1, giving [1, 3, 4b, 4a], and 4a now comes after 4b.

A stable variant inserts the minimum by shifting instead of swapping, but that costs O(n²) moves and loses selection sort's one advantage.

Stability: what happens to equal keys?

Interactive

Your input

Try

Input · letters show original order of equal keys

3a3b2a2b2c1

Insertion sort

12a2b2c3a3b
a before b

Bubble sort

12a2b2c3a3b
a before b

Selection sort

12a2b2c3b3a
Order broken

Shell sort

12b2c2a3a3b
Order broken
17.03.4

Dry run

Sorting [64, 25, 12, 22, 11].

  • Comparisons: 4 + 3 + 2 + 1 = 10 = n(n-1)/2. Swaps: 3.
iMinimum of arr[i..]SwapArray after
011 at index 4arr[0] ↔ arr[4][11, 25, 12, 22, 64]
112 at index 2arr[1] ↔ arr[2][11, 12, 25, 22, 64]
222 at index 3arr[2] ↔ arr[3][11, 12, 22, 25, 64]
325 at index 3none[11, 12, 22, 25, 64]
17.03.5

Complexity

The inner loop always runs to the end, so comparisons are exactly n(n-1)/2 for every input: sorted, reverse or random. Selection sort is not adaptive.

Best

O(n²)

Average

O(n²)

Worst

O(n²)

Space

O(1)

Practice ladder

Now try it yourself

Easy

  • Selection sort descending by selecting the maximum
  • Count comparisons for n = 10

Medium

  • Double-ended selection sort: place both the min and the max each pass
  • Stable selection sort using shifting

Advanced

  • Find the k smallest values using k selection passes and analyse the cost
  • Compute the minimum swaps to sort a permutation using cycles

Key takeaways

  • Always n(n-1)/2 comparisons, at most n - 1 swaps.
  • Not adaptive and not stable.
  • Useful when writes are expensive; otherwise insertion sort is usually better.