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

Слиянием двух упорядоченных множеств называется процесс упорядочения объединения данных множеств.

Теорема. Пусть даны два упорядоченных множества { A₁,…,A_N } и { B₁,…,B_N }. В рамках алгоритмов, основанных на простых сравнениях, данные множества нельзя слить быстрее, чем за 2 N-1 сравнение в худшем случае. Т.е. 2 N-1 является нижней оценкой времени работы алгоритма, если учитывать только время, расходуемой на сравнения элементов множеств, и если положить время одного сравнения равным 1.

Доказательство. Пусть для конкретных заданных множеств выполняются соотношения A_i< B_i и A_i+1> B_i. Тогда отсортированное объединение множеств выглядит следующим образом: {A₁, B₁, A₂, B₂ ,…, A_N,B_N }. Если хотя бы одно из приведенных 2N-1 соотношений не будет проверено, то найдется еще хотя бы одна перестановка элементов множества, удовлетворяющая всем приведенным соотношениям. Например, если не будет проверено соотношение A₂> B₁, то следующая последовательность будет удовлетворять всем остальным соотношениям:

{A₁, A₂, B₁, B₂ ,…, A_N,B_N }.

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

¢

Дословно так же доказывается следующая теорема

Теорема. Пусть даны два упорядоченных множества { A₁,…,A_{N +1}} и { B₁,…,B_N }. В рамках алгоритмов, основанных на простых сравнениях, данные множества нельзя слить быстрее, чем за 2 N сравнений элементов множества в худшем случае.

Алгоритм слияния. Пусть даны два упорядоченных множества { A₁,…,A_M} и { B₁,…,B_N }. Введем индексы i, j и k. Изначально i=1, j=1 и k=1.

Пока i£M и j£N:

Если A_i < B_j то

С_k++ = A_i++

Иначе

С_k++ = B_i++

Конец Если

Конец Цикла

Пока I £ M:

С_k++ = A_i++

Конец Цикла

Пока j £ N:

С_k++ = B_i++

Конец Цикла

Легко увидеть, что в данном алгоритме элементы множества сравниваются не более M+N-1 раз. Т.о. данный алгоритм оказывается строго оптимальным по числу сравнений элементов сортируемого множества (по крайней мере в алгоритмах, основанных на простых сравнениях).

Вопрос на понимание: можно ли два упорядоченных множества { A₁,…,A_N } и { B₁,…,B_N} слить быстрее чем за 2 N-1 операций сравнения в каком либо алгоритме, основанном операциях сравнения? … на операциях простого сравнения?

Алгоритм сортировки слиянием. Обозначим данный алгоритм Z(A₁,…,A_M), где { A₁,…,A_N } – сортируемое множество элементов. Алгоритм имеет следующий вид

Если число обрабатываемых элементов £ 1 то ВЫЙТИ

M₁ = [ M/2 ]; M₂ = M-M₁; // размеры половин массива

Z(A₁,…,A_M1 )

Z(A_M1+1,…,A_M)

Слить упорядоченные множества { A₁,…,A _M1 } и { A_M1+1,…,A_M } в массив B.

Скопировать массив B в массив { A₁,…,A_N }.

Легко видеть, что данный алгоритм решает задачу за время O(N log₂ N), где N – количество элементов в сортируемом массиве.

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

---

Дата добавления: 2015-10-30