Сортировки

Подробная информация по строчным методам
Программисты пользуются стандартными функциями сортировки из библиотеки языка.

Необходимо знать общее понимание о возможных вариантах сортировки
сортировка вставками
Элементы по очереди, слева направо, добавляются в отсортированную часть массива.

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)
пирамидальная сортировка
Метод сортировки сравнения, основанный на структуре данных двоичной кучи. Это похоже на сортировку выбором, где мы сначала находим минимальный элемент и помещаем минимальный элемент в начало. Повторяем тот же процесс для остальных элементов.

Двоичная куча — это законченное двоичное дерево, в котором элементы хранятся в особом порядке: значение в родительском узле больше (или меньше) значений в его двух дочерних узлах. Первый вариант называется max-heap, а второй — min-heap. Куча может быть представлена двоичным деревом или массивом.
Двоичное дерево

Входные данные: 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)
Функции Сортировки Python
Функции: arr.sort() или sorted_arr = sorted(arr)Timsort.

Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием.

  • По специальному алгоритму входной массив разделяется на подмассивы.
  • Каждый подмассив сортируется сортировкой вставками.
  • Отсортированные подмассивы собираются в единый массив с помощью модифицированной сортировки слиянием.
Характеристики:
  • Наилучшее время работы - O (n)
  • Среднее время работы — O (n log n)
  • Наибольшее время работы - O (n log n)
  • Затраты памяти - O (n)