Selection Sort
DSA · Sorting Algorithms
Theory
Selection sort divides the list into a sorted part on the left and an unsorted part on the right. On each pass it finds the smallest element in the unsorted part and swaps it into the next sorted position. It always performs O(n²) comparisons but at most n-1 swaps, which can matter when writes are expensive.
Why we use it
It is simple and makes the minimum number of swaps among basic sorts.
When to use it
Use it for teaching, very small lists, or when memory writes are costly. It is not stable in its basic form.
How it works
- Start: i = 0
- Find the minimum in arr[i..n-1]
- Swap it with arr[i]
- i < n - 1? Yes: i = i + 1, repeat. No: Array is sorted.
- Done
Syntax
for i in 0..n-1:
m = index of min(arr[i..n-1])
swap arr[i], arr[m]
Time: O(n²) always Space: O(1) Not stableExample
def selection_sort(arr):
n = len(arr)
for i in range(n):
m = i
for j in range(i + 1, n):
if arr[j] < arr[m]:
m = j
arr[i], arr[m] = arr[m], arr[i]
print("Placed", arr[i], "->", arr)
return arr
selection_sort([29, 10, 14, 37, 13])Key points
- Finds the minimum each pass
- At most n-1 swaps
- Always O(n²) comparisons
- Not stable by default