Обзор алгоритмов сортировки сортировка слиянием

Алгоритмы сортировки сортировка слиянием

Понять, как применить парадигму “разделяй и властвуй” для сортировки

Введение

Когда речь идет о сортировке, сортировка слиянием является одним из самых популярных алгоритмов. Он основан на известной парадигме “разделяй и властвуй”, при которой большая проблема разбивается на более мелкие проблемы, которые легче решить. Решения для них затем объединяются для исходной проблемы.

В этом руководстве мы рассмотрим детали реализации и оценим сложность сортировки слиянием в терминах нотации “Большое O”. Для лучшего понимания будет предоставлен пример.

Алгоритм

Идея алгоритма заключается в том, чтобы рекурсивно сортировать более маленькие подмассивы исходного массива. Когда несколько подмассивов отсортированы, они преобразуются в новый массив большего размера. Эта процедура продолжается до тех пор, пока мы не получим отсортированную версию исходного массива.

• Обзор алгоритмов сортировки Сортировка кучей
• Обзор алгоритмов сортировки Быстрая сортировка
• Использование нейроэволюции для инноваций в искусственном интеллекте

На первый взгляд это может показаться слишком сложным, но оказывается, что получение нового отсортированного массива на основе уже отсортированных массивов – это относительно быстрая процедура.

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

Функция слияния

Функция слияния принимает два отсортированных подмассива и возвращает новый отсортированный массив, состоящий из элементов обоих подмассивов. В приведенном ниже фрагменте кода передается массив элементов с двумя отсортированными подмассивами array[left, middle] и array[middle + 1, right].

Функция слияния

Мы проходимся по элементам обоих массивов с помощью двух указателей: i и j. Сравнивая элементы array[i] и array[j] на каждой итерации, мы добавляем меньший элемент в new_array. После этого указатель i или j увеличивается на 1 в зависимости от добавленного элемента, чтобы он указывал на следующий элемент.

Цикл продолжается до того момента, пока все элементы одного из подмассивов не будут добавлены в new_array. Затем мы просто добавляем оставшиеся элементы, содержащие большие значения другого подмассива.

Наконец, мы копируем каждый элемент отсортированного new_array в исходный массив. В результате, все элементы с индексами от left до right отсортированы в массиве.

Заметим, что для двух подмассивов длиной N мы проходимся линейно через каждый элемент только один раз. Это приводит к сложности O(N) для этого метода.

Пример слияния

Предположим, у нас есть массив, состоящий из двух отсортированных подмассивов array[0:3] и array[4:7]. Сначала мы инициализируем два указателя i и j, которые указывают на наименьшие элементы. В нашем случае они указывают на элементы с индексами 0 и 4 соответственно.

Итерация 1. Мы сравниваем array[0] = 2 и array[4] = 3. Поскольку 2 ≤ 3, мы сохраняем 2 как первый элемент нового массива и увеличиваем i на 1, чтобы он указывал на следующий возрастающий элемент, который равен 9.

Итерация 2. Мы сравниваем array[1] = 9 и array[4] = 3. Поскольку 9 > 3, мы сохраняем 3 как второй элемент нового массива и увеличиваем j на 1, чтобы он указывал на следующий возрастающий элемент, который равен 7.

Итерация 3. array[1] = 9 > array[5] = 7. Мы сохраняем 7 как следующий элемент. j увеличивается на 1.

…

Итерация 7. j указывает на конец правого массива. Это означает, что все элементы, начиная с индекса i в левом массиве, больше любого элемента в правом массиве. Следовательно, мы копируем все оставшиеся элементы (16 и 20) из правого массива в новый массив.

После завершения этой процедуры все отсортированные значения нового массива копируются в исходный массив.

Функция сортировки

Функция сортировки рекурсивно вызывает саму себя для отдельной сортировки левой и правой половин массива. Когда обе половины отсортированы, они объединяются после вызова функции merge_sort().

Функция сортировки слиянием

Для удобства клиента, первый вызов функции merge_sort() может быть обернут в другую функцию. Таким образом, клиенту не нужно передавать аргументы left и right функции, что успешно соответствует принципу инкапсуляции.

Обертка вызова сортировки слиянием в другую функцию

Пример

Иерархический вызов сортировки слиянием для массива из 8 элементов показан на рисунке ниже. Сначала мы делим массив на две равные части длиной 4. Для каждой из половин мы снова вызываем сортировку слиянием. Это приводит к массивам размером 2. Кстати, нет необходимости делить эти массивы снова, потому что любой массив, состоящий из одного элемента, всегда отсортирован.

Мы продолжаем алгоритм, сортируя массивы размером 2. Когда два последовательных массива размером 2 отсортированы, они объединяются в новый отсортированный массив длиной 4. Этот процесс продолжается для всех массивов размером 2. Когда два последовательных массива размером 4 отсортированы, они аналогично объединяются в новый отсортированный массив длиной 8.

Процесс завершается, когда все элементы отсортированы.

Сложность

Чтобы оценить сложность, нам сначала нужно понять структуру рекурсивных вызовов. Предположим, у нас есть массив размером N, который нужно отсортировать.

Мы делим этот массив на две половины размером N / 2. Обе половины затем делятся на две меньшие половины размером N / 4. В результате у нас получается 4 массива размером N / 4. Аналогично, на следующем уровне у нас получается 8 массивов размером N / 8. Мы продолжаем эту процедуру, пока не получим N массивов размером 1. Этот процесс иллюстрируется на следующем рисунке.

Для каждого из показанных массивов нам нужно вызвать процедуру слияния, которая требует времени O(K), где K – длина массива. Давайте вычислим общую временную сложность для каждого уровня массивов на рисунке выше.

• На первом уровне у нас есть один массив размером N, что требует времени O(N).
• На втором уровне у нас есть 2 массива размером N / 2. Каждый из этих массивов требует времени O(N / 2). Общее время составляет 2 * O(N / 2) = O(N).
• На третьем уровне у нас есть 4 массива размером N / 4. Каждый из этих массивов требует времени O(N / 4). Общее время составляет 4 * O(N / 2) = O(N).
• Последний уровень содержит N массивов размером 1. Каждый из этих массивов требует времени O(1). Общее время составляет N * O(1) = O(N).

Следуя этой логике, ясно, что каждый уровень требует времени O(N). Поскольку на каждом шаге каждый массив делится на две половины, легко заметить, что у нас есть O(logN) уровней. Это приводит к окончательной временной сложности O(N) * O(logN) = O(N * logN).

Преимущества

• Эффективность. Сортировка слиянием имеет сложность O(N * logN). Это лучшая возможная сложность среди всех алгоритмов сортировки, основанных на сравнении элементов массива. Однако во время процедуры слияния элементы должны быть временно отсортированы в другом массиве. Размер этого массива равен длине обоих подмассивов, что приводит к использованию O(N) памяти.
• Простота. По сравнению с другими эффективными алгоритмами сортировки, сортировка слиянием может быть легко интерпретирована и реализована.
• Стабильная сортировка. Если исходный массив содержит равные элементы, то алгоритм сортировки слиянием не изменит их относительное положение. Это важное свойство, которое используется более сложными алгоритмами, имеющими сортировку в своей реализации.

Заключение

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

Все изображения, если не указано иное, принадлежат автору