DSA — Sorting Algorithms

Selection Sort

Find the minimum of the unsorted portion and place it at the start. Minimises swaps.

— min read
O(n²)All Cases
O(1)Space
UnstableSort
MinSelection
SimpleIn-place
// SELECTION SORT — LIVE ANIMATION
Speed
Press ▶ Sort to begin
How It Works
Python Code
Complexity
Quiz
Practice
01
Find Minimum
Scan unsorted portion to locate minimum element.
min_idx = i
02
Swap
Swap the minimum with the first unsorted element.
arr[i], arr[min_idx] = arr[min_idx], arr[i]
03
Advance Boundary
Move sorted boundary one step right.
i += 1
04
Repeat
n-1 passes, always O(n²) comparisons but only O(n) swaps.
python 
def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
O(n²)
Always
Best and worst are identical
O(n)
Swaps
Only n swaps — good when writes are costly
O(1)
Space
In-place
Unstable
Equal elements
Swaps can change relative order
How many swaps does Selection Sort make in the worst case?
Progress 0 / 5 solved
5 problems · 3 PBC · 2 Startup
#215 Kth Largest Element in Array Google, Amazon PBC →
#75 Sort Colors Meta, Microsoft PBC →
#347 Top K Frequent Elements Amazon, Google PBC →
#1167 Minimum Cost to Connect Sticks Meesho STARTUP →
#179 Largest Number Razorpay STARTUP →
← Bubble Sort