Selection Sort
Learn how selection sort finds the minimum element each pass and places it at the front.
Selection Sort
Selection sort divides the array into a sorted left portion and an unsorted right portion. In each pass, it finds the minimum element from the unsorted portion and swaps it into its correct position at the front of the unsorted section. The sorted portion grows from left to right — exactly one element per pass.
How it works
def selection_sort(arr):
n = len(arr)
for i in range(n):
# find the minimum element in the unsorted portion
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# swap the found minimum with the first unsorted element
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arrHow it differs from bubble sort
Bubble sort makes many small swaps — potentially one per comparison. Selection sort makes exactly one swap per pass — it scans the entire unsorted section first to find the minimum, then does a single swap to place it. This makes it better when writing to memory is expensive, but it does not help with time complexity.
Pass 1: [5, 3, 8, 1, 9, 2]
scan unsorted [5,3,8,1,9,2] → min is 1 at index 3
swap arr[0] and arr[3]
→ [1, 3, 8, 5, 9, 2] ← 1 is sorted
Pass 2: [1 | 3, 8, 5, 9, 2]
scan unsorted [3,8,5,9,2] → min is 2 at index 5
swap arr[1] and arr[5]
→ [1, 2, 8, 5, 9, 3] ← 2 is sortedSelection sort always makes exactly n-1 swaps regardless of the input — compared to bubble sort's potentially O(n²) swaps. This is why selection sort can be preferable when swap cost is high, even though both algorithms have the same O(n²) time complexity.
Complexity
| Case | Time | Space |
|---|---|---|
| Best | O(n²) | O(1) |
| Average | O(n²) | O(1) |
| Worst | O(n²) | O(1) |
Unlike bubble sort, selection sort has no early-exit optimization — it always scans the full unsorted section even if the array is nearly sorted.