Сортировки

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key


if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6]
    insertion_sort(arr)
    print(arr)

def merge_sort(arr: list) -> None:
    if len(arr) > 1:
        # Нахождение середины массива
        mid = len(arr)//2
        # Разделение массива
        L = arr[:mid]
        R = arr[mid:]
        # Вызов метода для левой части
        merge_sort(L)
        # Вызов метода для правой части
        merge_sort(R)

        i = j = k = 0

        # Копирование элементов во временный массив
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # Проверка заполняемости
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1


if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6, 7]
    merge_sort(arr)
    print(arr)

def partition(array, low, high):
    '''Вспомогательня функция сравнения'''
    # Выбор опорного элемента
    pivot = array[high]
    # Выбор элемента
    i = low - 1

    # Проход массива и сравнение опорного элемента
    for j in range(low, high):
        if array[j] <= pivot:
            i = i + 1
            # Замена элемента в i на элемент в j
            (array[i], array[j]) = (array[j], array[i])
    # Поменять местами опорный элемент с большим элементом, указанным i
    (array[i + 1], array[high]) = (array[high], array[i + 1])
    # Вернуть позицию
    return i + 1


def quick_sort(array, low, high):
    if low < high:
        # Вызов вспомогательной функции сравнения
        shift = partition(array, low, high)
        # Рекурсивный вызов левой части
        quick_sort(array, low, shift - 1)
        # Рекурсивный вызов левой части
        quick_sort(array, shift + 1, high)


if __name__ == '__main__':
    array = [10, 7, 8, 9, 1, 5]
    quick_sort(array, 0, len(array) - 1)
    print(array)

Входные данные: 4, 10, 3, 5, 1
         4(0)
        /   \
     10(1)   3(2)
    /   \
 5(3)    1(4)
Числа в скобках представляют индексы в представлении данных в виде массива.
Применение функции к индексу 1:
         4(0)
        /   \
    10(1)    3(2)
    /   \
5(3)    1(4)
Применение функции к индексу 0:
        10(0)
        /  \
     5(1)  3(2)
    /   \
 4(3)    1(4)
Процедура heapify вызывает себя рекурсивно для создания кучи  сверху вниз.

def heapify(arr, n, i):
    '''Вспомогательная функция'''
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    # Сравнение левого элемента с корнем
    if left < n and arr[largest] < arr[left]:
        largest = left

    # Сравнение правого элемента с корнем
    if right < n and arr[largest] < arr[right]:
        largest = right

    # сдвинуть корень
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # Вызвать функцию с новым корнем
        heapify(arr, n, largest)


def heapSort(arr):
    n = len(arr)
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)

    # Извлечение элементов
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # swap
        heapify(arr, i, 0)


if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6, 7]
    heapSort(arr)
    print(arr)