Если вы устали читать сортировку слиянием и изучать ее из разных источников, то вы попали по адресу. Если вы здесь, я уверен, что вы думали о сортировке вещей больше, чем когда-либо прежде! По крайней мере, таков был мой опыт. Я еще не начал мечтать об алгоритмах сортировки, но ожидаю, что это скоро произойдет.
До сих пор вы могли узнать о некоторых наиболее распространенных — и иногда считающихся более простыми — алгоритмах сортировки: сортировка выбором, пузырьковая сортировка и сортировка вставками. Если вы внимательно посмотрите на эти алгоритмы, вы заметите общую черту: все они довольно медленные. Действительно, все алгоритмы сортировки, которые мы исследовали до сих пор, имеют одну общую черту: все они довольно неэффективны! Независимо от их причуд и различий, каждый из них имеет квадратичное время работы; другими словами, используя нотацию Big O, их время работы составляет O (n²).
Порядок, в котором мы изучаем эти темы, имеет решающее значение: возможно, вы рассмотрели алгоритмы сортировки на основе их временной сложности. До сих пор вы изучали алгоритмы с квадратичной сложностью выполнения, но теперь мы будем рассматривать алгоритмы, которые намного быстрее и эффективнее. И мы начнем с одного из самых интересных (хотя и немного более сложных) доступных алгоритмов сортировки!
Не волнуйтесь, мы будем учиться шаг за шагом. Первый шаг говорит вам, как называется этот алгоритм! Пришло время познакомиться с моим новым другом: сортировкой слиянием.
Алгоритмы «разделяй и властвуй»
Каждый из нас слышал о сортировке слиянием, упоминаемой в контексте технического интервью или учебника по компьютерным наукам. Большинство курсов тратят приличное время на изучение этой темы, и по той или иной причине этот конкретный алгоритм появляется довольно часто.
Сортировка слиянием — это алгоритм по принципу "разделяй и властвуй", изобретенный Джоном фон Нейманом в 1945 году. Сортировка слиянием по-прежнему является довольно новым алгоритмическим подходом к сортировке. Но подождите — мы еще не знаем, что это такое!
Пришло время дать определение — алгоритм сортировки слиянием разбивает несортированную коллекцию на две половины; он сортирует две половины, а затем объединяет их вместе, чтобы сформировать одну отсортированную коллекцию — и все это с использованием рекурсии.
Но пока придержите эту мысль — мы вернемся к рекурсии через мгновение.
Мы должны понимать, что основная идея сортировки слиянием заключается в следующем: гораздо эффективнее и проще сортировать два меньших отсортированных списка, чем сортировать один большой несортированный список.
Сортировка слиянием принципиально отличается от всех остальных алгоритмов сортировки тем, что является более эффективной.
Абстрактная идея сортировки слиянием называется разделяй и властвуй. Алгоритм, использующий стратегию «разделяй и властвуй», — это алгоритм, который делит проблему на более мелкие подзадачи. Простоон разбивает проблему на более простые версии.
Основные этапы алгоритма D&C можно разделить на три шага:
- алгоритм разделяй и властвуй делит проблему на более простые версии.
- Разбивая проблему на более мелкие части, ее становится легче решить. Обычно решение небольших подзадач может быть применено к более крупной и сложной.
- Преодоление большой проблемы с помощью одного и того же решения делает d+c рекурсивным.
Суть алгоритмов «разделяй и властвуй» заключается в том, что вы должны понять, как разделить проблему на более мелкие части. Разбивая проблему на подзадачи, ее становится намного легче решать. И обычно, когда вы понимаете, как решить подзадачу, вы можете применить это точное решение к более крупной проблеме. В этот момент в игру вступает рекурсия.
Обнаружение рекурсии в алгоритме
Полезность принципа «разделяй и властвуй» станет более очевидной, если мы сможем увидеть его в действии. Давайте посмотрим, как мы можем использовать рекурсию, чтобы разделить и победить иллюзорный алгоритм сортировки слиянием!
Мы понимаем, что сортировка слиянием разбивает несортированную структуру данных, сортирует две половины и объединяет их вместе.
Но как этот алгоритм действительно работает на практике?
Давайте начнем с простого примера, у нас есть массив из 8 элементов, начиная с 0-го индекса до 7-го индекса. А пока давайте попробуем понять, как в игру вступает методология «разделяй и властвуй». Здесь сначала нам нужно разделить и разбить проблему на наименьшие возможные «подзадачи» одного и того же типа. Итак, мы разбиваем 8 на 4, затем 4 на 2, затем еще 2 на 1. Когда у нас остается один список, это наша наименьшая возможная «подзадача» в нашей ситуации — это наш базовый случай — точка, в которой мы в основном решили нашу проблему. . С точки зрения сортировки элементов базовым случаем является отсортированный список.
В приведенном выше примере мы просто продолжали делить, пока не достигли стадии, когда мы не можем делить нашу подзадачу дальше. Начнем с одного несортированного списка. Затем мы разбиваем его на два несортированных списка. Мы можем разделить это еще дальше, на четыре списка. И затем мы можем снова разбить это на восемь списков. Теперь у нас есть восемь списков, и в каждом списке есть только один элемент.
Согласно d&c, мы знаем, что следующим шагом будет решение нашей наименьшей подзадачи. Как только мы сможем определить решение, которое работает для небольших подзадач, мы применим рекурсию для аналогичных более крупных подзадач.
Итак, давайте начнем с объединения двух элементов за раз с соседним элементом. Когда мы это сделаем, мы поместим элементы в правильном отсортированном порядке.
Мы взяли восемь отсортированных списков и объединили их вместе, чтобы создать четыре отсортированных списка. Затем мы взяли четыре списка и объединили их, чтобы сформировать два отсортированных списка.
Теперь у нас есть два отсортированных списка, мы можем завершить сортировку слиянием, объединив их вместе.
Почему это работает??
- список с одним элементом всегда будет считаться отсортированным.
- Когда у нас есть хотя бы два отсортированных списка, мы можем объединить их вместе, чтобы создать один отсортированный список.
- Разделив один большой несортированный список на отдельные части, мы можем затем начать объединять эти элементы вместе, эффективно реконструируя наш список, но теперь уже в отсортированном виде.
Есть несколько причин, по которым разделяй и властвуй так хорошо работает в реализации сортировки слиянием. Во-первых, тот факт, что список с одним элементом по определению является «отсортированным» списком, позволяет нам быстро определить, когда мы достигли нашей наименьшей возможной «подзадачи». Когда этот алгоритм реализован в коде, это становится случаем по умолчанию для определения того, когда рекурсия должна быть прекращена. Ранее мы обсуждали рекурсию в контексте бинарных деревьев; в этом случае базовым случаем является одиночный листовой узел, то есть когда вы не можете разбить поддерево на любые более мелкие части. Здесь применяется та же концепция: если мы не можем разделить наш список на какие-либо более мелкие части и у нас остается только один отсортированный элемент, мы достигли нашего рекурсивного базового случая.
Именно это делает рекурсию такой мощной: как только мы выяснили, как решить проблему слияния двух списков вместе, не имеет значения, состоит ли список из одного элемента или сотни — мы можем повторно использовать одну и ту же логику в обоих случаях. сценарии.
Рекурсия на работе
Мы знаем, что рекурсивный алгоритм — это алгоритм, который концептуально использует одно и то же решение для решения проблемы.
В коде Give, который был адаптирован из реализации сортировки слиянием Rosetta Code на JavaScript, мы видим здесь, что функция сортировки слиянием на самом деле вызывает себя.
Мы видим, что берем входной массив и разбиваем его как можно ближе к центру — в этом случае мы называем его midpoint. Затем мы берем эти две половины (leftArray и rightArray) и фактически передаем их в качестве новых входных массивов внутреннимвызовам mergeSort. Угадай, что? Это рекурсия в действии!
Функция mergeSort в конечном счете имеет внутри две функции:
- функция
merge, которая на самом деле объединяет два списка вместе и сортирует их в правильном порядке - и функция
mergeSort, которая будет продолжать разбивать входной массив снова и снова, рекурсивно, а также будет снова и снова вызыватьmerge, рекурсивно.
Действительно, поскольку сортировка слиянием реализуется рекурсивно, что делает ее быстрее, чем другие алгоритмы, которые мы рассматривали до сих пор.
