Персональные инструменты
 

Сортировка слиянием — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показаны 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

  1. REDIRECT discopal:Сортировка слиянием