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

Сортировка вставками

сортировка

O(n²) в худшем, O(n) для почти отсортированных. Вставляет каждый элемент на правильное место.

Синтаксис

def insertion_sort(arr):

Алгоритм учебный, но не бесполезный: Timsort внутри list.sort() досортировывает вставками короткие участки, потому что на почти упорядоченных данных они действительно близки к O(n). Сортировка устойчива — равные элементы сохраняют взаимный порядок, что важно, когда сортируют по одному ключу после другого. Питон-специфичная ловушка: если в условии внутреннего цикла забыть проверку j >= 0, отрицательный индекс не даст IndexError, а начнёт читать элементы с конца списка, и ошибка проявится молча — неверным результатом.

Примеры

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr
print(insertion_sort([12,11,13,5,6]))  # → [5,6,11,12,13]
# Трассировка
def ins_trace(arr):
    arr = arr[:]
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]; j -= 1
        arr[j+1] = key
        print(arr)
    return arr
ins_trace([4,3,1,2])
# Онлайн-алгоритм (добавление элементов)
def ins_insert(sorted_arr, x):
    i = len(sorted_arr)
    sorted_arr.append(x)
    while i > 0 and sorted_arr[i-1] > x:
        sorted_arr[i] = sorted_arr[i-1]
        i -= 1
    sorted_arr[i] = x
    return sorted_arr
result = []
for x in [3,1,4,1,5]:
    ins_insert(result, x)
print(result)  # → [1,1,3,4,5]
# Binary insertion sort
import bisect
def bin_ins_sort(arr):
    result = []
    for x in arr:
        bisect.insort(result, x)
    return result
print(bin_ins_sort([5,3,1,4,2]))  # → [1,2,3,4,5]
# Скорость на почти отсортированных данных
import random
arr = list(range(100))
arr[50] = -1  # один элемент не на месте
print(insertion_sort(arr[:])[:5])  # → [-1, 0, 1, 2, 3]

См. также

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