Слияние двух упорядоченных массивов

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

Пример сортировки слиянием. Сначала делим список на кусочки (по 1 элементу), затем сравниваем каждый элемент с соседним, сортируем и объединяем. В итоге, все элементы отсортированы и объединены вместе.
Автор Джон фон Нейман
Предназначение Алгоритм сортировки
Структура данных Массив
Худшее время O(n log2 n)
Лучшее время O(n log2 n)
Среднее время O(n log2 n)
Затраты памяти O(n) вспомогательных

Сортировка слиянием (англ. merge sort ) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Содержание

Подробный алгоритм сортировки [ править | править код ]

Для решения задачи сортировки эти три этапа выглядят так:

  1. Сортируемый массив разбивается на две части примерно одинакового размера;
  2. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
  3. Два упорядоченных массива половинного размера соединяются в один.

1.1. — 2.1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).

3.1. Соединение двух упорядоченных массивов в один.
Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два уже отсортированных по возрастанию подмассива. Тогда:
3.2. Слияние двух подмассивов в третий результирующий массив.
На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счётчики номеров элементов результирующего массива и подмассива, из которого был взят элемент, увеличиваем на 1.
3.4. «Прицепление» остатка.
Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.

Читайте также:  Склейка доменов с www и без

Пример сортировки на языке С

Реализация на языке C++11:

Реализация на языке С++14 с распараллеливанием от OpenMP

Итеративная реализация на языке C++:

Псевдокод алгоритма слияния без «прицепления» остатка на C++-подобном языке:

В приведённом алгоритме на C++-подобном языке используется проверка на равенство двух сравниваемых элементов подмассивов с отдельным блоком обработки в случае равенства. Отдельная проверка на равенство удваивает число сравнений, что усложняет код программы. Вместо отдельной проверки на равенство и отдельного блока обработки в случае равенства можно использовать две проверки if(L = R), что почти вдвое уменьшает код программы.

Псевдокод улучшенного алгоритма слияния без «прицепления» остатка на C++-подобном языке:

Число проверок можно сократить вдвое убрав проверку if(L >= R). При этом, в случае равенства L и R, L запишется в Out в первой итерации, а R – во второй. Этот вариант будет работать эффективно, если в исходном массиве повторяющиеся элементы не будут преобладать над остальными элементами.

Псевдокод сокращенного алгоритма слияния без «прицепления» остатка на C++-подобном языке:

Две операции пересылки в переменные L и R упрощают некоторые записи в программе, что может оказаться полезным в учебных целях, но в действительных программах их можно удалить, что сократит программный код. Также можно использовать тернарный оператор, что еще больше сократит программный код.
Псевдокод ещё более улучшенного алгоритма слияния без «прицепления» остатка на C++-подобном языке:

Время работы алгоритма порядка O(n * log n) при отсутствии деградации на неудачных случаях, которая является больным местом быстрой сортировки (тоже алгоритм порядка O(n * log n), но только для среднего случая). Расход памяти выше, чем для быстрой сортировки, при намного более благоприятном паттерне выделения памяти — возможно выделение одного региона памяти с самого начала и отсутствие выделения при дальнейшем исполнении.

Популярная реализация требует однократно выделяемого временного буфера памяти, равного сортируемому массиву, и не имеет рекурсий. Шаги реализации:

  1. InputArray = сортируемый массив, OutputArray = временный буфер
  2. над каждым отрезком входного массива InputArray[N * MIN_CHUNK_SIZE..(N + 1) * MIN_CHUNK_SIZE] выполняется какой-то вспомогательный алгоритм сортировки, например, сортировка Шелла или быстрая сортировка.
  3. устанавливается ChunkSize = MIN_CHUNK_SIZE
  4. сливаются два отрезка InputArray[N * ChunkSize..(N + 1) * ChunkSize] и InputArray[(N + 1) * ChunkSize..(N + 2) * ChunkSize] попеременным шаганием слева и справа (см. выше), результат помещается в OutputArray[N * ChunkSize..(N + 2) * ChunkSize], и так для всех N, пока не будет достигнут конец массива.
  5. ChunkSize удваивается
  6. если ChunkSize стал >= размера массива, то конец, результат в OutputArray, который (ввиду перестановок, описанных ниже) есть либо сортируемый массив, либо временный буфер, во втором случае он целиком копируется в сортируемый массив.
  7. иначе меняются местами InputArray и OutputArray перестановкой указателей, и всё повторяется с пункта 4.
Читайте также:  Разность двух множеств это

Такая реализация также поддерживает размещение сортируемого массива и временного буфера в дисковых файлах, то есть пригодна для сортировки огромных объёмов данных. Реализация ORDER BY в СУБД MySQL при отсутствии подходящего индекса устроена именно так (источник: filesort.cc в исходном коде MySQL).

Пример реализации алгоритма простого двухпутевого слияния на псевдокоде:

Есть несколько вариантов функции merge(), наиболее простой вариант может выглядеть так:

Достоинства и недостатки [ править | править код ]

  • Работает даже на структурах данных последовательного доступа.
  • Хорошо сочетается с подкачкой и кэшированием памяти.
  • Неплохо работает в параллельном варианте: легко разбить задачи между процессорами поровну, но трудно сделать так, чтобы другие процессоры взяли на себя работу, в случае если один процессор задержится.
  • Не имеет «трудных» входных данных.
  • Устойчивая – сохраняет порядок равных элементов (принадлежащих одному классу эквивалентности по сравнению).
  • На «почти отсортированных» массивах работает столь же долго, как на хаотичных. Существует вариант сортировки слиянием, который работает быстрее на частично отсортированных данных, но он требует дополнительной памяти, в дополнении ко временному буферу, который используется непосредственно для сортировки.
  • Требует дополнительной памяти по размеру исходного массива.

Задача

Имеются два упорядоченных по возрастанию (предыдущий элемент меньше последующего) массива. Требуется получить третий упорядоченный по возрастанию массив, путем слияния первых двух.

Решение

Например. Если
1-й массив: 4, 8, 12, 14, 23, 85,
а 2-й массив: 2, 4, 8, 9, 12, 16,
тогда 3-й массив будет таким: 2, 4, 4, 8, 8, 9, 12, 12, 14, 16, 23, 85.

Алгоритм и особенности решения задачи.

  1. Для начала надо определиться, как у нас будут формироваться первые два массива. Использование random нам не подходит, т.к. массивы должны быть упорядоченными. Будем вводить данные с клавиатуры.
  2. Длина третьего массива равна сумме двух первых.
  3. Элементы под текущими для каждого массива индексами сравниваются, и меньший по значению записывается в третий массив. При этом индекс массива, из которого элемент был скопирован в третий массив, должен увеличиться.
  4. Может возникнуть ситуация, когда один массив закончился, а второй еще нет. Поэтому в программе должен быть организован цикл записи возможного окончания как первого так и второго массива.
Читайте также:  Программа для разгадывания капчи

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

А лгоритм слияния отсортированных массивов в один отсортированный массив является одним из самых простых алгоритмов. Он используется в качестве вспомогательного инструмента в других алгоритмах (например, сортировке слиянием).

Пусть есть два массива a и b, размерами m и n соответственно. Массивы отсортированы по возрастанию. Необходимо слить массивы в один массив c размером (m + n). Определим для массивов новый тип T и макрос CMP_LT, необходимый для сравнения элементов.

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

Для того, чтобы слить массивы, отсортированные в обратном порядке, очевидно, нужно поменять макрос на CMP_GT, проводящий сравнение на больше.

Галопирующий режим

П усть имеется два массива a и b следующего вида

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

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>