Основные алгоритмы сортировки. Разбираемся с танцами (это не шутка)

Два распространенных алгоритма могут ускользать от понимания. В чем отличие разбиения в быстрой сортировке и похожих «магических» движений в сортировке слиянием? Меня это долго сбивало с толку. Разберемся же с ними наконец!

Быстрая сортировка

В основе работы этого алгоритма лежит принцип «разделяй и властвуй». Опорный элемент перемещается на такую позицию, что все элементы слева от него меньше или равны ему, а все элементы справа — больше или равны. Затем соседние части рассматриваются как отдельные массивы и определение опорного элемента повторяется в каждом из них. Так продолжается до тех пор, пока все элементы исходного массива не окажутся упорядоченными. Ничто не объясняет процесс лучше, чем видео, созданное в румынском Университете Сапиентия, Тыргу-Муреш (Марошвашархей).

Для выбора опорного элемента Существует несколько стратегий. Можно начинать с первой или последней ячейки, брать центральную или же вообще случайную.

def partition(arr, low, high):
    # В качестве опорного элемента выбираем последний
    pivot = arr[high]

    # Указатель на больший элемент
    i = low - 1

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

    # Меняем местами ячейки с опорным элементом и с первым бо́льшим его элементом
    arr[i + 1], arr[high] = arr[high], arr[i + 1]

    # Возвращаем указатель на разделяющую ячейку
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        # Находим элемент опоры таким образом, чтобы элементы, которые меньше его,
        # располагались слева, а те, что больше — справа
        pivot_index = partition(arr, low, high)

        # Рекурсивно применяем этот алгоритм к подмассивам слева и справа
        # от опорного элемента
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

# Пример использования
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr) - 1)

# Выводим отсортированный массив
print("Sorted array:", arr)

Вывод:

Sorted array: [1, 5, 7, 8, 9, 10]

Разберем пример подробнее

1. Отправляем весь массив в quick_sort с параметрами low = 0 и high = 5.

2. Проверяем, что low < high. Если так, вызывается функция partition, которая вычисляет опорный элемент (pivot) и по его положению разбивает исходный массив. При выделении двух подмассивов мы подразумеваем, что все элементы больше опорного располагаются справа, а меньшие — слева.

3. Итак… partition вызывается со всем массивом, low = 0 и high = 5.

Начальный массив: [10, 7, 8, 9, 1, 5], где low = 0, high = 5.

Опорная точка: arr[high] = arr[5] = 5.

Индекс i = low − 1 = 0 – 1 = –1.

Теперь цикл идет от low к high−1, то есть от 0 до 4.

• j = 0, arr[j] = 10, что не меньше pivot (5), поэтому ничего не делаем.
• j = 1, arr[j] = 7, что так же не менее pivot, ничего не делаем.
• j = 2, arr[j] = 8, аналогично — ничего.
• j = 3, arr[j] = 9, то же самое.
• j = 4, arr[j] = 1 — теперь значение меньше pivot (5), поэтому мы увеличиваем i на 1 (становится 0) и меняем местами arr[i] и arr[j]. Теперь i = 0, а arr = [1, 7, 8, 9, 10, 5]. Это важный шаг, который надо понять до конца.

После цикла i = 0 и arr = [1, 7, 8, 9, 10, 5].

Мы меняем местами i+1 и high, поэтому arr становится [1, 5, 8, 9, 10, 7].

Значение i+1 равно 1. Теперь обратите внимание, что все числа, которые меньше 5, находятся слева, а все числа, которые больше 5, — справа. Значение опорного элемента — 5, а его индекс — 1.

4. Итак, ячейка 1 хранит опорный элемент со значением 5. Массив: [1, 5, 8, 9, 10, 7]. Теперь мы вызываем quick_sort для левого и правого подмассивов. Это следующий важный шаг.

5. Продолжаем рекурсивно вызывать quick_sort для левого и правого подмассивов, пока не достигнем базового случая, где low >= high.

Временна́я сложность:

• лучшее значение: T(N) = 2T(N/2) + O(N) ⇒ O(N log N),
• худшее: T(N) = T(N−1) + O(N) ⇒ O(N²),
• среднее: O(N log N).

Пространственная сложность:

• среднее значение: O (log N) — из-за стека рекурсии,
• худшее: O (N).

Сортировка слиянием

И этот алгоритм придерживается принципа «разделяй и властвуй». Мы так же делим массив на две половины, сортируем их рекурсивно, а затем объединяем. Еще одно превосходное видео, которое, как я считаю, хорошо объясняет последовательность действий:

В отличие от предыдущего случая, никакой опорной точки нет. Мы просто делим массив на две половины, рекурсивно вызываем сортировку слиянием, а позже объединяем все части.

# Использование словаря levels для отслеживания массивов — интересный
# способ визуализации, но не более. Он не является частью самого алгоритма.
levels = {}

def merge_sort(arr, level):
    """
    Рекурсивно разбиваем массив на половинки и отслеживаем уровни.
    Отсортированные половинки объединяем вместе.
    """

    # Сохраним массив текущего уровня
    if level not in levels:
        levels[level] = []

    levels[level].append(arr.copy())  # Сохраняем копию

    # Базовый случай: если массив пустой или есть только один элемент, то сортировать нечего.
    if len(arr) > 1:
        mid = len(arr) // 2  # Находим середину

        # Разбиваем массив на две половинки.
        left_half = arr[:mid]
        right_half = arr[mid:]

        # Рекрурсивно применяем алгоритм к каждой из половинок.
        merge_sort(left_half, level + 1)
        merge_sort(right_half, level + 1)

        # Соединяем отсортированные половинки.
        merge(arr, left_half, right_half)

def merge(arr, left_half, right_half):
    """
    Объединяем два осортированных подмассива (left_half и right_half) в единый массив.
    """
    i = j = k = 0  # Инициализируем индексы для left_half, right_half и единого массива.

    # Сравниваем значения двух половинок и соединяем упорядоченно.
    while i < len(left_half) and j < len(right_half):
        if left_half[i] < right_half[j]:
            arr[k] = left_half[i]
            i += 1
        else:
            arr[k] = right_half[j]
            j += 1
        k += 1

    # Копируем оставшиеся элементы в left_half
    while i < len(left_half):
        arr[k] = left_half[i]
        i += 1
        k += 1

    # Также поступаем с оставшимися ячейками в right_half
    while j < len(right_half):
        arr[k] = right_half[j]
        j += 1
        k += 1

# Пример
arr = [10, 7, 8, 9, 1, 5]

# Выпоняем сортировку, отслеживаем уровни.
merge_sort(arr, 0)

# Смотрим, как массив разделяется на каждом уровне.
for level in levels:
    print("Level:", level, ", Arrays:", levels[level])

# Отсортированный массив.
print("Final Sorted Array:", arr)

Вывод:

Level: 0 , Arrays: [[10, 7, 8, 9, 1, 5]]
Level: 1 , Arrays: [[7, 8, 10], [1, 5, 9]]
Level: 2 , Arrays: [[10], [7, 8], [9], [1, 5]]
Level: 3 , Arrays: [[7], [8], [1], [5]]
Final Sorted Array: [1, 5, 7, 8, 9, 10]

Подробнее

1. Отправляем весь массив в merge_sort с уровнем равным 0.

2. Обратите внимание, выводим массив до проверки длины — так мы увидим его состояние на каждом уровне.

3. Состояние массива на каждом уровне сохраняем в словаре, который называется levels.

4. Проверяем, не является ли массив базовым случаем с одним элементом (или вообще пустым). Так есть смысл делить его пополам.

5. Рекурсивно вызываем merge_sort для левой и правой половин, увеличивая уровень на 1.

Это самый важный шаг: мы продолжаем рекурсивно вызывать merge_sort для левой и правой половин, пока не достигнем базового случая с единичной длиной. После того, как рекурсивные вызовы отработали, можно производить слияние.

Но где же происходит сортировка?.. В функции слияния!

6. Наконец объединяем две половины с помощью функции слияния.

Сначала рассмотрим базовый случай — например, [7] и [8], которыми на верхнем уровне оперировала функция merge_sort на левой и правой половинках. Здесь все просто: когда выполняется слияние, элементы просто сравниваются и получают позиции в правильном порядке.

Другой вариант — слияние половинок из нескольких элементов. Для примера можно взять половинки [7,8,10] и [1,5,9], которые обрабатывались merge_sort на верхнем уровне. При слиянии сначала сравнивается 7 и 1 — первой размещается 1. Затем сравнивается 7 и 5 — после 1 размещается 5. Доходит очередь до сравнения 7 и 9 — на этот раз 7 становится после 5.

Временна́я сложность:

• Лучшее, худшее и среднее значение: T(N) = 2 · T(N/2) + O(N) ⇒ O(N log N).

Пространственная сложность:

• O (N) — из‑за необходимости дополнительных массивов.

Сравнение быстрой сортировки и сортировки слиянием

И быстрая сортировка, и сортировка слиянием — эффективные алгоритмы, но у них разные характеристики и предпочтительные варианты использования. Вот небольшая таблица для лучшего понимания:

Быстрая сортировка: разбивка (partitioning) — активный процесс. Основная работа происходит до рекурсивных вызовов для подмассивов.

Сортировка слиянием: разбивка проще — массив просто делится пополам. Основная работа происходят на этапе слияния после того, как рекурсивные вызовы уже отсортировали подмассивы.