Selection Sort

A sorting algorithm that finds the smallest element on each pass and moves it to the front.

#How does it work?

Selection sort thinks of the array as two parts: a sorted part on the left and an unsorted part on the right. At first the sorted part is empty.

Each pass scans the unsorted part and finds its smallest element. That element is swapped with the first element of the unsorted part, so the sorted part grows by one.

Unlike bubble sort, it makes only one swap per pass. The number of comparisons, however, is always the same, even if the array is already sorted.

#Live animation

$ selection_sort --visualizespace · ← → · r · sStep 1/52

Each pass finds the smallest element of the unsorted part and moves it to the front.

Speed

Comparisons: 0Swaps: 0Current minimumComparingSwappingIn place

for i = 0 to n - 2
  min = i
  for j = i + 1 to n - 1
    if a[j] < a[min]: min = j
  swap(a[i], a[min])

#Step by step

01Treat the first element of the unsorted part as the minimum for now.
02Compare the remaining elements with it one by one; whenever you find a smaller one, it becomes the new minimum.
03When the scan ends, swap the minimum with the first element of the unsorted part.
04The sorted part has grown by one; continue from the next element.
05When only one element is left unsorted, the array is sorted.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def selection_sort(a: list[int]) -> None:
    n = len(a)
    for i in range(n - 1):
        # Find the smallest element of the unsorted part a[i:].
        smallest = i
        for j in range(i + 1, n):
            if a[j] < a[smallest]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]


numbers = [5, 1, 4, 2, 8, 3]
selection_sort(numbers)
print(*numbers)

#Complexity

Best	O(n²)
Average	O(n²)
Worst	O(n²)
Extra memory	O(1)
Stable?	No
In place?	Yes

It always makes about n²/2 comparisons, because finding the minimum means looking at every remaining element. On the other hand it makes at most n-1 swaps, which helps when writes are expensive. Because it swaps distant elements it is not stable: equal elements can change order.

#When to use it?

Useful when you want few swaps (e.g. when writing to memory is expensive) or for very small arrays. For larger data, or when stability matters, merge sort or insertion sort is a better choice.

#Practice

Easy

1/3

What does selection sort do on each pass?

1Finds the smallest unsorted element and moves it to the front
2Compares and swaps neighbours
3Splits the array in half
4Partitions around a pivot

1–4 pick · ← → move · enter continue

Medium

1/1

What does [29, 10, 14, 37, 13] look like after the first pass?

1[10, 29, 14, 37, 13]
2[10, 13, 14, 29, 37]
3[10, 14, 29, 37, 13]
4[29, 10, 14, 13, 37]

1–4 pick · ← → move · enter continue

Hard

1/1

Why is selection sort not stable?

1It swaps distant elements, so equal elements can change order
2It uses extra memory
3It is recursive
4It stops early on sorted arrays

1–4 pick · ← → move · enter continue

#Up next

Lessons that build on this one:

Heap Sort