all Python 3Algorithms & data structuresterm

Selection sort

sorting

O(n²). It finds the smallest item and puts it where it belongs. The number of swaps is minimal (O(n)).

Syntax

def selection_sort(arr):

Unlike insertion or bubble sort it has no fast case: the full scan of the remaining tail happens every time, so an already sorted list still costs O(n²) comparisons. What it does buy is exactly O(n) swaps, one per position, and that is the only practical reason to remember it — situations where writing is more expensive than reading. The classic swap-with-the-minimum implementation is not stable: equal items can trade places, which rules it out for sorting by several keys in succession.

Examples

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
print(selection_sort([64,25,12,22,11]))  # → [11,12,22,25,64]
# Трассировка
def sel_trace(arr):
    arr = 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]
        print(arr)
    return arr
sel_trace([3,1,4,2])
# Descending
def sel_desc(arr):
    n = len(arr)
    for i in range(n):
        max_idx = i
        for j in range(i+1, n):
            if arr[j] > arr[max_idx]:
                max_idx = j
        arr[i], arr[max_idx] = arr[max_idx], arr[i]
    return arr
print(sel_desc([3,1,4,1,5]))  # → [5,4,3,1,1]
# Подсчёт шагов
def sel_steps(arr):
    n = len(arr); comparisons = 0
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            comparisons += 1
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return comparisons
print(sel_steps([5,4,3,2,1]))  # → 10 сравнений для n=5
# Selection sort всегда O(n²) независимо от входных данных
print(selection_sort([1,2,3,4,5]))  # → [1,2,3,4,5] (уже отсортирован)

See also

Open in the full glossarydocs.python.orgReport an inaccuracy