Loading...
Selection Sort divides the array into a sorted and an unsorted region. On each pass it scans the unsorted region for the minimum value and swaps it into place. It always does O(n²) comparisons but at most n swaps, which matters when writes are expensive.
Selects the smallest remaining element and moves it to the front.
| Best case | O(n²) |
| Average case | O(n²) |
| Worst case | O(n²) |
| Space | O(1) |
| Stable | No |
Complexities are for the reference implementation shown; constant factors and cache behavior vary by language.
Idiomatic, copy-paste implementations. Pick your language:
Python
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_i = i
for j in range(i + 1, n):
if arr[j] < arr[min_i]:
min_i = j
arr[i], arr[min_i] = arr[min_i], arr[i]
return arrSorting [5, 1, 4, 2] step by step:
The control flow of the algorithm as a diagram: