An in-place comparison sort that divides the list into a sorted and an unsorted part, repeatedly picking the smallest element from the unsorted part.
Overview
The mechanism
Scan the entire unsorted region to find its minimum. Swap that minimum with the first unsorted position. That position is now finished and never moves again. Shrink the unsorted region by one and repeat.
Where insertion sort takes the next element and finds its place, selection sort takes the next place and finds its element. That inversion is the whole difference, and it explains every performance property below.
Parameters
15
Visualization
Step: 0
Click Randomize or Step to begin sorting.
Algorithm Insight
Selection Sort builds the sorted array by repeatedly finding the minimum element from the unsorted part.
1.Set the first unsorted position as the current Minimum.
2.Scan the rest of the unsorted part for a smaller value.
3.If found, update the Minimum index.
4.Swap the found minimum with the first unsorted element.
Complexity
Average CaseO(N²)
Space ComplexityO(1)
Selection Sort: A Practical Guide
Find the smallest remaining element, swap it into place, repeat. Always quadratic - but it performs the fewest writes of any comparison sort, which is the one thing it is genuinely best at.
Work one through by hand
Sort [29, 10, 14, 37, 13].
Pass 1: min of all five is 10 → swap with 29 → [10, 29, 14, 37, 13]
Pass 2: min of last four is 13 → swap with 29 → [10, 13, 14, 37, 29]
Pass 3: min of last three is 14 → already in place → [10, 13, 14, 37, 29]
Pass 4: min of last two is 29 → swap with 37 → [10, 13, 14, 29, 37]
Four passes, 4 + 3 + 2 + 1 = 10 comparisons, and 3 swaps. The comparison count is fixed by the array size; only the swap count depends on the data.
Why it is quadratic no matter what
Pass 1 scans n elements, pass 2 scans n−1, and so on:
(n−1) + (n−2) + … + 1 = n(n−1)/2 → O(n²)
Critically this holds for every input. Finding a minimum requires examining every candidate, and the algorithm has no way to notice that the array is already sorted — it still scans the whole remaining region to confirm the minimum. Best case, average case and worst case are all Θ(n²), which makes selection sort strictly worse than insertion sort on nearly-sorted data.
The compensation is the write count. Selection sort performs at most n−1 swaps — O(n) writes, one per position. Insertion sort and bubble sort both perform O(n²) writes.
Find the smallest, put it in place, repeat
Selection sort scans the unsorted region for the smallest element and swaps it into the boundary position. The sorted region grows by one each pass.
Sorting [64, 25, 12, 22, 11]:
Pass
Smallest found
Swap
Result
1
11
with 64
[11, 25, 12, 22, 64]
2
12
with 25
[11, 12, 25, 22, 64]
3
22
with 25
[11, 12, 22, 25, 64]
4
25
already there
[11, 12, 22, 25, 64]
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
smallest = i
for j in range(i + 1, n):
if arr[j] < arr[smallest]:
smallest = j
if smallest != i:
arr[i], arr[smallest] = arr[smallest], arr[i]
return arr
Note that the inner loop finds an index, not a value, and only one swap happens per pass. That is the algorithm's one genuine advantage.
The one thing it is good at
Algorithm
Comparisons
Swaps / writes
Selection
O(n²) always
O(n) — at most n−1
Bubble
O(n²)
O(n²)
Insertion
O(n²)
O(n²) shifts
Selection sort performs at most n−1 swaps, whatever the input. Every other quadratic sort performs O(n²) moves.
That matters when writing is far more expensive than comparing:
Flash memory and EEPROM, where each write consumes a limited erase cycle.
Very large records moved by value rather than by pointer.
Write-through caches or logged storage, where each write has a fixed overhead.
Outside those cases, its always-O(n²) comparison count makes it the weakest of the three. Insertion sort is O(n) on sorted input; selection sort is O(n²) on every input, because it always scans the whole unsorted region regardless of order.
Not adaptive, not stable
Two properties selection sort lacks, and both follow from how it works.
Not adaptive. The inner loop always scans everything. Sorted input takes exactly as long as random input — there is no early exit to add, because the algorithm cannot know the minimum without looking.
Not stable. The swap moves a distant element into position i, jumping over anything in between. Two equal elements can therefore be reordered:
Sorting [3a, 3b, 1] — pass 1 finds 1 and swaps it with 3a, giving [1, 3b, 3a]. The two equal 3s have swapped relative order.
A stable variant exists: instead of swapping, shift the intervening elements right and insert — but that reintroduces O(n²) writes, which was the only reason to use selection sort. The stable version has no advantage over insertion sort.
Property
Selection
Insertion
Bubble
Adaptive
No
Yes
Yes
Stable
No
Yes
Yes
Swaps
O(n)
O(n²)
O(n²)
In place
Yes
Yes
Yes
The one thing it is best at, and the one thing it gets wrong
Selection sort loses to insertion sort on almost every measure, so it is worth being precise about the single column where it wins -- and about the property it quietly lacks, which is the reason it is never the sort in a standard library.
example_01.pyPython
def selection(a):
a = a[:]
comps = swaps = 0
for i in range(len(a)):
m = i
for j in range(i + 1, len(a)):
comps += 1
if a[j] < a[m]:
m = j
if m != i:
a[i], a[m] = a[m], a[i]
swaps += 1
return a, comps, swaps
def bubble(a):
a = a[:]
comps = swaps = 0
for i in range(len(a) - 1):
for j in range(len(a) - 1 - i):
comps += 1
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swaps += 1
return a, comps, swaps
import random
random.seed(3)
data = random.sample(range(30), 30)
_, sc, ss = selection(data)
_, bc, bs = bubble(data)
print("30 random elements")
print(" selection: %3d comparisons, %3d writes" % (sc, ss))
print(" bubble: %3d comparisons, %3d writes" % (bc, bs))
# Same comparison count, wildly different write count. Selection sort
# never makes more than n-1 swaps, because each pass puts one element in
# its final position and leaves it there.
print()
print("%6s %10s %8s" % ("n", "swaps", "n-1"))
for n in (10, 50, 100, 500):
d = random.sample(range(n), n)
_, _, s = selection(d)
print("%6d %10d %8d" % (n, s, n - 1))
# At most n-1, every time, for any input. That is the property worth
# knowing: when a WRITE is far more expensive than a comparison --
# flash memory with limited erase cycles, or records that are large to
# move -- minimising writes is the thing that matters, and this is the
# simple sort that does it.
#
# Now the flaw. Selection sort is NOT stable, and unlike bubble sort's
# case this is not a one-character fix: the long-distance swap is the
# algorithm.
items = [("Ada", 2), ("Bala", 1), ("Chen", 2), ("Dara", 1)]
def selection_pairs(x):
x = x[:]
for i in range(len(x)):
m = i
for j in range(i + 1, len(x)):
if x[j][1] < x[m][1]:
m = j
x[i], x[m] = x[m], x[i]
return x
print()
print("input: ", [p[0] for p in items])
print("sorted: ", [p[0] for p in selection_pairs(items)])
# Bala and Dara both have key 1, and Ada and Chen both have key 2. Read
# the output: the two 2s come out as Chen then Ada -- reversed from the
# input. The second pass swapped Ada to the end to bring Dara forward,
# throwing it past Chen, and nothing
# afterwards can put it back. Sorting twice to break ties -- by one key,
# then another -- silently fails on a sort that does this.
Output
Things to try
Watch the scan, then the single swap. Set Array Size to 15 and press Next Step. Each pass sweeps the whole unsorted region looking for a minimum, then makes exactly one swap. The scanning is where all the time goes.
Confirm the sorted region never changes. Once a cell joins the sorted block on the left it is never touched again. Contrast with bubble sort, where elements keep moving until the very end.
Give it sorted input and watch it not care. Press Randomize Array until the array looks close to ascending, then Auto-Run. The comparison count is identical to a shuffled array — only the swaps drop. No other sort on this track is this indifferent to its input.
Count the swaps. Run a full sort at Array Size 30 and note the swap count stays at or below 29, while the comparison count climbs past 400. That ratio is the entire argument for using it.
The one situation where it wins
When writes are dramatically more expensive than reads, minimising them matters more than minimising comparisons. That is the case for EEPROM and flash memory, where each cell tolerates a limited number of erase cycles, and for any sort where moving an element means copying a large record rather than an integer.
Selection sort guarantees at most n−1 writes. Cycle sort pushes this to the theoretical minimum and is the specialist choice, but selection sort gets most of the benefit with far simpler code.
What trips people up
Swapping on every comparison. The minimum’s index should be tracked through the scan and swapped once at the end. Swapping each time a smaller element appears turns the O(n) write advantage — the only reason to use it — back into O(n²).
Assuming it is stable. It is not. Sorting [2a, 2b, 1] swaps the 1 with the first 2, putting 2b before 2a. Stability requires the shifting variant, which forfeits the low write count.
Expecting sorted input to be fast. Unlike insertion sort, there is no early exit and no adaptivity. Sorted input costs exactly as many comparisons as random input.
Skipping the self-swap check. When the minimum is already in position the swap is a no-op; guarding it costs one comparison and saves a write, which matters given that low writes are the point.
The short version
Selection sort makes n−1 passes, each finding the minimum of what remains, giving Θ(n²) comparisons on every input and no benefit from partially sorted data. What it does offer is at most n−1 swaps — the fewest writes of any simple comparison sort. On ordinary in-memory data insertion sort beats it on every axis; on write-limited storage that swap count is the reason to choose it anyway.
Its useful relative: heap sort
Selection sort's structure — repeatedly extract the minimum — is exactly what a heap accelerates.
Finding the minimum by scanning is O(n), giving O(n²) overall. Finding it in a heap is O(log n), giving O(n log n).
That is heap sort: build a heap in O(n), then extract the extreme element n times. Same algorithm, better data structure, and it is genuinely competitive:
Selection sort
Heap sort
Find the extreme
O(n) scan
O(log n) heap
Total
O(n²)
O(n log n)
In place
Yes
Yes
Stable
No
No
Practical use
Rare
Introsort's fallback
Heap sort is the guaranteed-O(n log n) fallback inside introsort, used when quick sort's recursion gets too deep. So selection sort's idea does appear in production — with a heap in place of the linear scan.
That progression is a good illustration of a general point: the algorithm and the data structure are separable, and improving the structure can change the complexity class without changing the logic.
Selection as a partial problem
Selection sort's first k passes give the k smallest elements, sorted. That makes it O(nk) for the top-k problem, which is better than O(n log n) sorting when k is very small.
Better options exist:
A heap of size k gives O(n log k) — push each element, pop when the heap exceeds k. This is what heapq.nlargest does.
Quickselect finds the k-th smallest in O(n) expected time using quick sort's partitioning, without sorting anything else.
So even for its natural partial-sorting niche, selection sort is dominated. The honest position: it is a teaching algorithm whose only real advantage is minimal writes, and that advantage matters in a narrow set of hardware situations.
Common mistakes
Swapping inside the inner loop rather than after it, which turns the O(n) swap count into O(n²) and gives away the one advantage.
Tracking the minimum value instead of its index, so the swap cannot be performed.
Adding an early-exit flag, which cannot help — the algorithm has no way to detect sortedness.
Expecting stability. It has none, and reordering equal elements can matter in multi-key sorting.
Using it on real data.sorted() is orders of magnitude faster.
Questions people ask
Why use selection sort at all? Only when writes are far more expensive than comparisons — flash memory, or moving very large records.
Is it stable? No. The long-distance swap reorders equal elements.
Why is it O(n²) even on sorted input? Because the inner loop must scan the whole unsorted region to know the minimum. Order is invisible to it.
How does it compare with bubble sort? Same comparisons, far fewer swaps, and no best case. Bubble sort is adaptive and stable; selection sort is neither.
What is heap sort's relationship to it? The same repeated-extraction idea with a heap instead of a scan, giving O(n log n).
Is it good for finding the k smallest? O(nk), which beats sorting for tiny k — and a size-k heap or quickselect beats it.
Recap in one screen
Scan the unsorted region for the minimum, swap it into place, repeat.
At most n−1 swaps — the only quadratic sort with linear writes.
Always O(n²) comparisons: not adaptive, because it cannot detect sortedness.
Not stable, because the swap jumps over intervening elements.
Replace the linear scan with a heap and it becomes heap sort at O(n log n).
Run it in Python
Selection sort's defining trait is that it makes exactly n − 1 swaps no matter what you feed it. The program counts both comparisons and swaps so you can see one stay fixed while the other does not.
selection_sort.pyPython 3
# Selection sort: find the smallest remaining item, put it in place, repeat.
def selection_sort(a, show=True):
a = a[:]
n = len(a)
comparisons = swaps = 0
for i in range(n - 1):
smallest = i
for j in range(i + 1, n): # scan the unsorted tail
comparisons += 1
if a[j] < a[smallest]:
smallest = j
if smallest != i:
a[i], a[smallest] = a[smallest], a[i]
swaps += 1
if show:
print(f"i={i}: picked {a[i]:>3} -> {a}")
return a, comparisons, swaps
data = [64, 25, 12, 22, 11, 90]
print("start :", data)
out, c, s = selection_sort(data)
print("sorted:", out)
print(f"{c} comparisons, {s} swaps")
print()
for name, sample in [("sorted", [1, 2, 3, 4, 5, 6]),
("reversed", [6, 5, 4, 3, 2, 1]),
("random", [3, 6, 1, 5, 2, 4])]:
_, c, s = selection_sort(sample, show=False)
print(f"{name:>9}: {c} comparisons, {s} swaps")
print()
print("The comparison count never moves. That is selection sort.")
Output
How the code works
smallest = iAssume the first unsorted item is the minimum, then try to disprove it. Tracking the index rather than the value is what lets the swap at the end be a single operation.
for j in range(i + 1, n):The scan always covers the entire unsorted tail, with no early exit available — you cannot know something is the minimum without looking at everything. Hence n(n−1)/2 comparisons, always.
if smallest != i:Skips the swap when the item is already where it belongs. It saves a write, not a comparison, so it does not change the complexity.
swapsAt most n − 1 swaps for any input. Where a write is expensive — flash memory, or records far larger than the key — that is a real advantage over bubble or insertion sort.
Change one thing
Feed it an already sorted list. The comparison count is identical to the reversed case: selection sort cannot detect that it has no work to do.
Track the largest instead of the smallest and fill from the right. Same algorithm, mirrored — and a good check that you have followed it.
Sort [2, 2, 1] and follow the two 2s. Their order flips, which is why selection sort is not stable while insertion sort is.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
How many comparisons does selection sort make on an already sorted list of n items?
There is no early exit available: you cannot know an item is the minimum without checking every remaining one. The count is fixed by n alone.
What selection sort is genuinely good at:
One swap per position, whatever the input. Where writes are expensive - flash memory, or records much larger than the key - that is a real advantage.
Sorting [2, 2, 1] with this implementation:
The first 2 is swapped with the 1 at the far end, jumping it past the second 2. Selection sort is not stable; insertion sort is.
Cheat sheet
Selection Sort
An in-place comparison sort that divides the list into a sorted and an unsorted part, repeatedly picking the smallest element from the unsorted part.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.