WikiSysop: 1 версия

2008-10-23T16:48:21Z

1 версия

Новая страница

Алгоритм сортировки слиянием применяется для [[сортировка|сортировки]], если есть возможность использовать для хранения промежуточных результатов память, сравнимую с размером исходного массива.

Слияние — это объединение двух или более упорядоченных
массивов в один упорядоченный. Пусть требуется упорядочить массив по убыванию.
Для этого сравниваются два наименьших элемента обоих массивов и наименьший
из них выводится как наименьший элемент суммарного массива, затем
процедура повторяется (см. процедуру «merge» в представленном ниже алгоритме).
Нетрудно видеть, что слияние двух упорядоченных последовательностей ''A'' и ''B''
длин ''|A|'' и ''|B|'' происходит за ''O(|A|+|B|)'' сравнений.

Теперь рассмотрим алгоритм сортировки слиянием. Исходный массив ''A'' длины ''n'' делится пополам.
Затем производится рекурсивная сортировка каждой половинки и их слияние.
Пусть ''T(n)'' — число сравнений, достаточное для сортировки слиянием, тогда будет справедливо
рекуррентное соотношение:
<m>
T(n) \leq 2T(n/2)+O(n).
</m>

Решив это соотношение, получаем, что сложность алгоритма асимптотически оптимальна — алгоритм сортирует входной массив за время ''O(n log n)'' для любых входных данных. Однако алгоритм сортировки слиянием редко применяется на практике, т. к. в процессе своей работы алгоритм активно использует дополнительные массивы, что редко допустимо в реальных приложениях.
<code-python>
def mergesort(L):
print funcname(),L
if len(L) < 2:
return L
return merge(mergesort(L[:len(L)/2]),mergesort(L[len(L)/2:]))

def merge(A,B):
print funcname(),A,B,
Out = []
while len(A)+len(B) > 0:
if len(B) == 0 or (len(A) > 0 and A[0] < B[0]):
Out.append(A[0])
A = A[1:]
else:
Out.append(B[0])
B = B[1:]
print " -> ", Out
return Out
</code-python>

Sorting: [3, 4, 1, 5, 9, 2, 6, 5, 3, 5]
mergesort: [3, 4, 1, 5, 9, 2, 6, 5, 3, 5]
mergesort: [3, 4, 1, 5, 9]
mergesort: [3, 4]
mergesort: [3]
mergesort: [4]
merge: [3] [4] -> [3, 4]
mergesort: [1, 5, 9]
mergesort: [1]
mergesort: [5, 9]
mergesort: [5]
mergesort: [9]
merge: [5] [9] -> [5, 9]
merge: [1] [5, 9] -> [1, 5, 9]
merge: [3, 4] [1, 5, 9] -> [1, 3, 4, 5, 9]
mergesort: [2, 6, 5, 3, 5]
mergesort: [2, 6]
mergesort: [2]
mergesort: [6]
merge: [2] [6] -> [2, 6]
mergesort: [5, 3, 5]
mergesort: [5]
mergesort: [3, 5]
mergesort: [3]
mergesort: [5]
merge: [3] [5] -> [3, 5]
merge: [5] [3, 5] -> [3, 5, 5]
merge: [2, 6] [3, 5, 5] -> [2, 3, 5, 5, 6]
merge: [1, 3, 4, 5, 9] [2, 3, 5, 5, 6] -> [1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
Sorted: [1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

[[Category:Алгоритмы]]
{{replicate-from-custiswiki-to-lib}}

Сортировка слиянием - История изменений

WikiSysop: 1 версия