Sorting Algorithms
Selection Sort
Selection sort divides the array into a sorted left portion and an unsorted right portion. On each pass it selects the minimum element from the unsorted portion and swaps it into its correct sorted position.
How It Works
Text
Array: [5, 3, 8, 1, 2]
sorted | unsorted
Pass 1: find min in [5,3,8,1,2] → 1 at index 3
swap arr[0] and arr[3] → [1, 3, 8, 5, 2]
Pass 2: find min in [3,8,5,2] → 2 at index 4
swap arr[1] and arr[4] → [1, 2, 8, 5, 3]
Pass 3: find min in [8,5,3] → 3 at index 4
swap arr[2] and arr[4] → [1, 2, 3, 5, 8]
Pass 4: find min in [5,8] → 5 at index 3
already in place, swap arr[3] and arr[3]
Result: [1, 2, 3, 5, 8]Implementation
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]
return arr
nums = [5, 3, 8, 1, 2]
print(selection_sort(nums)) # [1, 2, 3, 5, 8]Step-by-step Trace
Python
def selection_sort_verbose(arr):
arr = 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
arr[i], arr[min_idx] = arr[min_idx], arr[i]
print(f"Pass {i+1}: placed {arr[i]} at index {i} → {arr}")
return arr
selection_sort_verbose([5, 3, 8, 1, 2])
# Pass 1: placed 1 at index 0 → [1, 3, 8, 5, 2]
# Pass 2: placed 2 at index 1 → [1, 2, 8, 5, 3]
# Pass 3: placed 3 at index 2 → [1, 2, 3, 5, 8]
# Pass 4: placed 5 at index 3 → [1, 2, 3, 5, 8]Selection Sort vs Bubble Sort
| Property | Selection Sort | Bubble Sort |
|---|---|---|
| Swaps | O(n) — exactly one per pass | O(n²) — swap on every comparison |
| Comparisons | O(n²) always | O(n²) worst; O(n) best |
| Early exit | No — always n passes | Yes — exits if no swap in a pass |
| Stable | No (default) | Yes |
| Write operations | Fewer — good for flash memory | More writes |
When does selection sort win?
Selection sort performs at most n−1 swaps regardless of the input. If swaps are expensive (e.g. writing to flash storage where writes wear out cells), selection sort is preferable to bubble sort even though both are O(n²).
Complexity Table
| Case | Time | Space | Note |
|---|---|---|---|
| Best case | O(n²) | O(1) | No early exit — always scans everything |
| Average case | O(n²) | O(1) | |
| Worst case | O(n²) | O(1) | |
| Swaps | O(n) | — | At most n−1 swaps |
| Stable | No | — | Swapping can change order of equal elements |