Selection sort visualization

Selection sort is a sorting algorithm that builds the sorted list from the left. On each pass it scans the unsorted part to find the smallest value and swaps it into the next free position.

How it works

1. Treat the whole array as unsorted. Set i = 0.
2. Scan indexes i to the end and remember the position of the smallest value.
3. Swap that value with the one at index i, unless it is already there.
4. Move i one step to the right and repeat until only one element is left.

A worked example of selection sort

Sort [5, 2, 6, 1, 4, 3]. Each pass finds the smallest value in the unsorted part and puts it at the front of that part:

1. Smallest of indexes 0 to 5: 1 at index 3 (5 comparisons). Swap it with index 0: [1, 2, 6, 5, 4, 3].
2. Smallest of indexes 1 to 5: 2 at index 1 (4 comparisons). Already in place: [1, 2, 6, 5, 4, 3].
3. Smallest of indexes 2 to 5: 3 at index 5 (3 comparisons). Swap it with index 2: [1, 2, 3, 5, 4, 6].
4. Smallest of indexes 3 to 5: 4 at index 4 (2 comparisons). Swap it with index 3: [1, 2, 3, 4, 5, 6].
5. Smallest of indexes 4 to 5: 5 at index 4 (1 comparison). Already in place: [1, 2, 3, 4, 5, 6].

In total: 15 comparisons and 3 swaps. The comparisons would be the same for any order of these six values; only the swaps vary. The last value, 6, needs no pass of its own: when one element is left it must already be in place.

Selection sort pseudocode

Indexes start at 0, as in the code of this lesson. A is the array and n is its length.

SELECTION-SORT(A, n)
1  for i = 0 to n - 2
2      min = i
3      for j = i + 1 to n - 1
4          if A[j] < A[min]
5              min = j
6      if min != i
7          exchange A[i] with A[min]

The inner loop always runs to the end of the array, which is why the comparison count never changes. The test on line 6 only skips a pointless swap.

Time and space complexity

Finding the minimum of m values takes m - 1 comparisons, and it always scans the whole unsorted part, whatever the order of the input. Adding that up gives n(n - 1)/2 comparisons every time.

Complexity

Best case time	O(n²)
Average case time	O(n²)
Worst case time	O(n²)
Extra space	O(1)

• Best, O(n²): even a sorted array needs the full scan on every pass.
• Average, O(n²): the comparison count does not depend on the order of the data.
• Worst, O(n²): the same number of comparisons as the other cases.
• Space, O(1): it sorts in place.

What makes it different is the number of swaps: at most one per pass, so at most n - 1 in total. Bubble sort can swap on almost every comparison.

Stability

This version is not stable. Swapping the minimum into place can jump an element over another one with the same value, changing their relative order. For example, sorting [2a, 2b, 1] swaps 2a with 1 and leaves 2b before 2a.

When to use it, and when not to

Use it when writes are much more expensive than comparisons, because it makes at most n - 1 swaps. Otherwise insertion sort is usually the better simple choice, since it adapts to sorted input and selection sort never does. For large data, use an O(n log n) algorithm.

Where selection sort is used

Like bubble sort, it is seldom the final choice in production code. Its three useful roles are about what it does well or what it leads to:

• Media where writes are costly. Writing to flash memory wears the cells, so an algorithm that never makes more than n - 1 swaps, whatever the order of the input, can be worth its O(n²) comparisons on small data.
• Taking the smallest values only. Stop after k passes and the first k positions hold the k smallest values in order, after roughly k × n comparisons. This beats a full sort when k is tiny.
• The idea inside heap sort. Heap sort is selection sort that finds the next value with a heap in O(log n) time instead of a scan. Knuth presents it in section 5.2.3, "Sorting by selection", for that reason.

Common mistake and edge cases

Related algorithms and variations

A bidirectional version finds both the smallest and the largest value in each scan and fills both ends, which halves the number of passes. A stable version shifts the elements between the two positions instead of swapping, which keeps equal values in order but costs more writes, so it loses the algorithm's one advantage.

The closest relatives are bubble sort (bubble sort vs selection sort) and insertion sort (selection sort vs insertion sort). To keep the idea and drop the O(n²), compare it with heap sort in selection sort vs heap sort.