Python Tutorial
Selection Sort
Repeatedly select the smallest remaining element and place it at the front of the unsorted part.
How Selection Sort Works
Divide the list into a sorted part (initially empty) at the front and an unsorted part behind it. On each pass, scan the unsorted part for the minimum and swap it into the first unsorted position. After k passes the first k elements are final.
It always makes O(n²) comparisons but performs at most n−1 swaps — useful when writing to memory is expensive.
Implementation
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j # track the smallest so far
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(selection_sort([64, 25, 12, 22, 11]))
# [11, 12, 22, 25, 64]Step-by-Step
Sorting [64, 25, 12, 22, 11]:
| Pass | Min found | Array after swap |
|---|---|---|
| 1 | 11 | [11, 25, 12, 22, 64] |
| 2 | 12 | [11, 12, 25, 22, 64] |
| 3 | 22 | [11, 12, 22, 25, 64] |
| 4 | 25 | [11, 12, 22, 25, 64] |
Complexity
| Metric | Value |
|---|---|
| Comparisons (all cases) | O(n²) |
| Swaps | O(n) — at most n−1 |
| Space | O(1) in place |
| Stable? | No (the standard swap version) |
Selection vs Bubble vs Insertion
- Selection: fewest swaps (good when writes are costly), but never better than O(n²) comparisons.
- Bubble: many swaps; O(n) best case if optimized.
- Insertion: excellent on nearly-sorted data, O(n) best case, and stable.
Selection sort minimizes the number of writes to the array — a real advantage on hardware like flash memory where writes wear out cells.
Best Practices
- Use it to teach the "find-the-minimum" pattern, not for production sorting.
- Prefer it over bubble sort when write count matters more than comparison count.
- For real code, use
sorted()/list.sort().
Try It Yourself
Exercise 1: How many swaps (at most) does selection sort perform on n elements?
Show solution
At most n − 1 — one swap per pass. This is its key advantage when writes are expensive.
Exercise 2: Is standard selection sort stable?
Show solution
No — swapping distant elements can change the relative order of equal keys.
📘 Real-World Deep Dive
Knowing <strong>DSA Selection Sort (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.
Real-Life Scenario
An end-to-end usage of DSA Selection Sort that you'd actually see in a data pipeline or analytics notebook.
Real-Life Example
def selection(xs):
for i in range(len(xs)):
m = i
for j in range(i+1, len(xs)):
if xs[j] < xs[m]: m = j
xs[i], xs[m] = xs[m], xs[i]
return xs
print(selection([29, 10, 14, 37, 13]))Expected Output
(see source)Common mistakes
- Off-by-one errors in binary-search: the standard idiom is
while lo <= hiwithmid = (lo + hi) // 2. - Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
- Comparison algorithms (
sorted(iterable)) are stable by default in Python — surprising for Java/C++ users. - Treating DSA Selection Sort as a black box without reading the docs — the API has subtle defaults that bite when you scale.
🚀 Performance & Best Practices
- Use
bisect.bisect_left/bisect_rightinstead of writing your own binary search. - Convert a sorted search into a tuple-access pattern with
numpy.searchsortedfor huge arrays. - Use
heapqfor priority queues instead of maintaining a sorted list manually. - When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.
🧪 Try It Yourself
- Reproduce the snippet on a representative slice of your own data.
- Profile the snippet with
cProfileortimeitand find the single biggest improvement. - Generalise the snippet into a small, reusable function you can drop into future projects.