Selection sort
Selection sort consists of iterations. In the -th iteration, it finds the smallest element among the unsorted suffix and swaps it into position . After iterations, the first elements are in their final sorted positions.
For a = [5, 3, 8, 1, 9, 2]:
in all cases — unlike bubble sort, there is no early exit optimization because the inner loop always runs fully to find the minimum.
def selection_sort(a):
n = len(a)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if a[j] < a[min_index]:
min_index = j
a[i], a[min_index] = a[min_index], a[i]
a = [5, 3, 8, 1, 9, 2]
selection_sort(a)
print(a) # [1, 2, 3, 5, 8, 9]
i=0: min is 1 at index 3 → swap a[0] and a[3] → [1, 3, 8, 5, 9, 2]
i=1: min is 2 at index 5 → swap a[1] and a[5] → [1, 2, 8, 5, 9, 3]
i=2: min is 3 at index 5 → swap a[2] and a[5] → [1, 2, 3, 5, 9, 8]
i=3: min is 5 at index 3 → no swap needed → [1, 2, 3, 5, 9, 8]
i=4: min is 8 at index 5 → swap a[4] and a[5] → [1, 2, 3, 5, 8, 9]