Итеративный, MergeSort на месте
Для моего класса алгоритмов нам было поручено написать реализацию сортировки слиянием, которая является итеративной, а не рекурсивной, и вместо того, чтобы требовать другой массив. Так как это для класса, я не хочу, чтобы мне давали какой-либо код, но я не могу понять основной алгоритм того, что делать. Поиск в Google не дает ничего, кроме кода или объяснений, которые я не понимаю, так что это не помощь.
В настоящее время я понимаю, что нужно отсортировать все подмассивы размера 1 (что, конечно, тривиально), затем объединить подмассивы размера 2, размера 4 и т. Д., Но это кажется гораздо ближе к сортировке вставкой, а затем это вопрос, как использовать постоянное количество дополнительного пространства.
В заключение, я не имею права использовать какие-либо стандартные библиотечные функции или классы C++, такие как векторы, стеки, любые виды и т. Д.
2 ответа
Итеративный алгоритм, использующий сортировку слиянием типа сортировки для сортировки массива на месте, может выглядеть следующим образом.
Давайте возьмем этот несортированный массив в качестве примера:
4, 3, 8, 5, 9, 2, 5, 1, 7, 10, 8, 0, 3
Алгоритм будет иметь внешний цикл по размеру объединенных массивов. Таким образом, в начале этот размер равен 1 (еще ничего не было объединено). Затем на каждой итерации этот размер удваивается, что фактически объединяет два уже отсортированных последовательных сегмента вместе.
Фактическое объединение будет использовать два индекса в сегменте, который должен быть объединен: по одному в начале каждого из двух сегментов, которые должны быть объединены.
Пока значение левого индекса меньше или равно другому значению, левый индекс увеличивается (перемещается вправо). В другом случае выполняется самая сложная операция в этом алгоритме:
Значения между двумя индексами сдвигаются вправо, а крайний правый из них (значение во втором индексе) перемещается в первый индекс. Таким образом, значения вращаются вокруг одной позиции. После этого цикла оба индекса увеличиваются.
Этот процесс повторяется до тех пор, пока либо левый индекс не достигнет правого индекса, либо правый индекс не достигнет конца второго сегмента (который может быть концом массива). Когда это происходит, объединение завершается, и два сегмента будут рассматриваться как один на следующей итерации внешнего цикла.
Вот некоторые изображения, иллюстрирующие эти шаги в том виде, как они будут выполнены на данных примера:
Здесь объединение выполняется для создания сегментов второго размера. Иногда последний сегмент не будет иметь полный размер, но это не проблема. Для каждого из цветных сегментов размещаются два индекса, один указывает на первое из двух значений, а другой - на второе значение. Если первое значение больше второго, они меняются местами. В случае свопа оба индекса увеличиваются, и второй индекс достигает конца второго сегмента (который был только шириной в 1 значение), и поэтому объединение заканчивается. В случае, если не происходит свопинга, увеличивается только первый индекс, но он достигает второго, поэтому слияние также заканчивается (без внесения изменений).
Это становится более интересным во второй итерации внешнего цикла:
Первые сегменты, которые будут соединены, это [3 4] и [5 8]. Два индекса указывают на 3 и 5 соответственно (подчеркнуты синим цветом). Левый индекс увеличивается до тех пор, пока соответствующее значение не будет больше значения второго индекса. В этом случае это означает, что первый индекс достигает второго без каких-либо изменений. Для второй пары сегментов есть еще много работы:
Теперь [2 9] и [1 5] необходимо объединить. Когда 2 больше 1, включается циклическая операция: 1 нужно сдвинуть, толкая 2 и 9 на одну позицию вправо. Оба индекса увеличиваются. Теперь 2 не больше, чем другое значение (5), поэтому увеличивается только первый индекс. Наконец, 9 больше 5, поэтому их нужно поменять местами, и затем объединение будет завершено для этих сегментов.
Аналогичная последовательность операций выполняется для следующей пары сегментов:
Последняя "пара" сегментов действительно не имеет второго сегмента: второй индекс указывает за конец массива, поэтому объединение немедленно прекращается.
Снова внешний цикл повторяется, удваивая размер сегмента. Теперь необходимо объединить следующее:
Обратите внимание, как 1 (на втором указателе) сдвинут до [3 4 5 8], которые все перемещаются на одну позицию вправо, чтобы освободить место для этого. То же самое происходит с 2: он снова сдвигается до тех же 4 значений. Но затем мы находим, что 3 не больше пяти, и первый индекс увеличивается до тех пор, пока он не укажет на 8. Там 5 вводится до 8. Наконец, 8 не больше 9, поэтому второй индекс достигает конечной точки.
Я не буду представлять то же самое для другого сегмента, и заключительную итерацию внешнего цикла, которая сделает еще одно слияние.
Как вы и просили, я не предоставляю код;-)
Некоторые соображения
Хотя это можно назвать сортировкой слиянием, циклическое изменение значений в действительности отрицательно сказывается на эффективности исходного алгоритма в худшем случае. Правда, количество сравнений остается прежним, но количество ходов может быть больше. Возьмите, например, значения [3 4 5 8], которые перемещаются дважды, чтобы освободить место для перемещения 1 и перемещения 2. Это уже составляет 10 ходов (и объединение на этом шаге еще не завершено), в то время как исходная сортировка объединения всегда будет делать то же количество ходов, что и значения в объединяемых сегментах. В лучших случаях этот алгоритм не требует никаких движений или меньше, чем исходный алгоритм.
Этот метод гарантирует стабильную сортировку.
Вы упоминаете постоянное пространство и на месте.
Если сортировка слиянием на месте не должна быть стабильной, вы можете менять местами элементы, а не перемещать их между массивами. Выполните сортировку слиянием в левой половине массива в правую половину массива, поменяв местами объединенный вывод с правой половиной массива так, чтобы объединенный вывод оказался в правой половине массива, и что было в правая половина массива переставляется на левую половину массива, переупорядочивается (это нестабильная часть), но не сортируется.
Объедините сортировку 2-го квартала в 1-й квартал массива, чтобы 1-й квартал заканчивался отсортированными данными, а 2-й квартал заканчивался переупорядоченными, но несортированными данными. Затем объедините первую четверть со второй половиной массива в массив, начиная с начала второй четверти, снова поменявшись местами во время операции объединения. Последние 3/4 массива заканчиваются сортировкой, а первый массив 1/4 переупорядочивается и не сортируется.
Слейте сортировку 2-го восьмого в 1-ю восьмую, затем объедините сортировку 1-го восьмого с последними 3/4 массива, получив в итоге последние 7/8 отсортированных и первые 1/8 переупорядоченных, но не отсортированных
Продолжайте до тех пор, пока слева не останется один или два несортированных элемента. Их можно установить, выполнив частичную сортировку вставки для одного или двух элементов.
Если используется постоянное пространство и сортировка слиянием должна быть стабильной, вы можете использовать сортировку по принципу "снизу вверх", перемещая часть массива в постоянное пространство, объединяясь с теперь освобожденным пространством в массиве, затем перепаковывая массив, чтобы заполнить один или два пробела, оставленные процессом слияния, и повторяйте до тех пор, пока не достигнете последней оставшейся освобожденной части массива, после чего вы можете выполнить обычную сортировку слиянием, используя постоянное пространство и освобожденную часть массива. Это завершает один проход сортировки слиянием.