|
Сортировка слиянием — различия между версиями
Материал из CustisWiki
|
|
| (не показаны 3 промежуточные версии 2 участников) | | Строка 1: |
Строка 1: |
| − | Алгоритм сортировки слиянием применяется для [[сортировка|сортировки]], если есть возможность использовать для хранения промежуточных результатов память, сравнимую с размером исходного массива.
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | | + | |
| − | Слияние — это объединение двух или более упорядоченных
| + | |
| − | массивов в один упорядоченный. Пусть требуется упорядочить массив по убыванию.
| + | |
| − | Для этого сравниваются два наименьших элемента обоих массивов и наименьший
| + | |
| − | из них выводится как наименьший элемент суммарного массива, затем
| + | |
| − | процедура повторяется (см. процедуру «merge» в представленном ниже алгоритме).
| + | |
| − | Нетрудно видеть, что слияние двух упорядоченных последовательностей ''A'' и ''B''
| + | |
| − | длин ''|A|'' и ''|B|'' происходит за ''O(|A|+|B|)'' сравнений.
| + | |
| − | | + | |
| − | Теперь рассмотрим алгоритм сортировки слиянием. Исходный массив ''A'' длины ''n'' делится пополам.
| + | |
| − | Затем производится рекурсивная сортировка каждой половинки и их слияние.
| + | |
| − | Пусть ''T(n)'' — число сравнений, достаточное для сортировки слиянием, тогда будет справедливо
| + | |
| − | рекуррентное соотношение:
| + | |
| − | <math>
| + | |
| − | T(n) \leq 2T(n/2)+O(n).
| + | |
| − | </math>
| + | |
| − |
| + | |
| − | Решив это соотношение, получаем, что сложность алгоритма асимптотически оптимальна — алгоритм сортирует входной массив за время ''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}} | + | |
Текущая версия на 20:45, 13 июня 2011
- REDIRECT discopal:Сортировка слиянием
|
 |
