все Python 3Алгоритмы и структуры данныхпонятие

Сортировка выбором

сортировка

O(n²). Находит минимальный элемент и ставит на нужное место. Минимум обменов (O(n)).

Синтаксис

def selection_sort(arr):

В отличие от вставок и пузырька, здесь нет быстрого случая: полный проход по остатку делается всегда, поэтому даже на уже отсортированном списке те же O(n²) сравнений. Зато обменов ровно O(n) — по одному на позицию, и это единственная практическая причина о ней помнить: когда запись дороже чтения. Классическая реализация через обмен с минимумом неустойчива — равные элементы могут поменяться местами, так что для сортировки по нескольким ключам подряд она не подходит.

Примеры

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] (уже отсортирован)

См. также

Открыть в полном глоссарииdocs.python.orgСообщить о неточности