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

StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»

2011-06-13T17:45:30Z

Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»

WikiSysop: 1 версия

2008-10-23T16:48:21Z

1 версия

StasFomin: обновление данных

2008-10-22T15:44:16Z

обновление данных

WikiSysop: 1 версия

2008-08-04T09:55:53Z

1 версия

BenderBot: реплицировано из внутренней CustisWiki

2005-10-17T17:16:16Z

реплицировано из внутренней CustisWiki

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

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

Слияние — это объединение двух или более упорядоченных
массивов в один упорядоченный. Пусть требуется упорядочить массив по убыванию.
Для этого сравниваются два наименьших элемента обоих массивов и наименьший
из них выводится как наименьший элемент суммарного массива, затем
процедура повторяется (см. процедуру «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}}

StasFomin в 11:22, 17 октября 2005

2005-10-17T11:22:23Z

← Предыдущая	Версия 09:55, 4 августа 2008
(не показана 1 промежуточная версия 1 участника)
(нет различий)

@@ Строка 1: / Строка 1: @@
-Алгоритм сортировки слиянием применяется для [[сортировка|сортировки]], если есть возможность использовать для хранения промежуточных результатов память, сравнимую с размером исходного массива.
+#REDIRECT [[discopal:{{PAGENAME}}]]
-−
-Слияние — это объединение двух или более упорядоченных
-массивов в один упорядоченный. Пусть требуется упорядочить массив по убыванию.
-Для этого сравниваются два наименьших элемента обоих массивов и наименьший
-из них выводится как наименьший элемент суммарного массива, затем
-процедура повторяется (см. процедуру «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}}

← Предыдущая	Версия 16:48, 23 октября 2008
(нет различий)

← Предыдущая	Версия 11:22, 17 октября 2005
(нет различий)