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

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

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

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

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

 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) — активный процесс. Основная работа происходит до рекурсивных вызовов для подмассивов.

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