Sortuj przez scalanie

Sortuj przez scalanie

Przykład sortowania przez scalanie. Najpierw podziel listę na najmniejszą jednostkę (1 element), a następnie porównaj każdy element z sąsiednią listą, aby posortować i scalić dwie sąsiednie listy. Na koniec wszystkie elementy są sortowane i łączone.
Klasa	Algorytm sortowania
Struktura danych	Szyk
Wydajność w najgorszym przypadku	${\ Displaystyle O (n \ log n)}$
Najlepsza wydajność	${\ Displaystyle \ Omega (n \ log n)}$ typowy, naturalny wariant ${\ Displaystyle \ Omega (n)}$
Średnia wydajność	${\ Displaystyle \ Theta (n \ log n)}$
Złożoność przestrzeni w najgorszym przypadku	${\ Displaystyle O (n)}$ łącznie z ${\ Displaystyle O (n)}$ pomocniczy, ${\ Displaystyle O (1)}$ pomocniczy z połączonymi listami

W informatyce sortowanie przez scalanie (również powszechnie pisane jako mergesort ) jest wydajnym algorytmem sortowania ogólnego przeznaczenia i opartym na porównaniach . Większość implementacji generuje stabilne sortowanie , co oznacza, że ​​kolejność równych elementów jest taka sama na wejściu i wyjściu. Sortowanie przez scalanie to algorytm typu „dziel i rządź” , który został wynaleziony przez Johna von Neumanna w 1945 roku. Szczegółowy opis i analiza sortowania przez scalanie od dołu do góry pojawiła się w raporcie Goldstine'a i von Neumanna już w 1948 roku.

Algorytm

Koncepcyjnie sortowanie przez scalanie działa w następujący sposób:

1. Podziel nieposortowaną listę na n list podrzędnych, z których każda zawiera jeden element (listę zawierającą jeden element uważa się za posortowaną).
2. Wielokrotnie scalaj listy podrzędne, aby utworzyć nowe posortowane listy podrzędne, aż pozostanie tylko jedna podlista. To będzie posortowana lista.

Implementacja odgórna

Przykładowy kod podobny do C wykorzystujący indeksy dla algorytmu sortowania przez scalanie od góry do dołu, który rekurencyjnie dzieli listę ( w tym przykładzie zwaną przebiegami ) na listy podrzędne, dopóki rozmiar listy podrzędnej nie wyniesie 1, a następnie scala te listy podrzędne w celu utworzenia posortowanej listy. Kroku kopiowania wstecz można uniknąć, zmieniając kierunek scalania z każdym poziomem rekurencji (z wyjątkiem początkowej jednorazowej kopii, której również można uniknąć). Aby to zrozumieć, rozważmy tablicę z dwoma elementami. Elementy są kopiowane do B[], a następnie scalane z powrotem do A[]. Jeśli istnieją cztery elementy, po osiągnięciu dna poziomu rekurencji pojedyncze przebiegi elementów z A [] są scalane z B [], a następnie na następnym wyższym poziomie rekurencji te dwuelementowe przebiegi są łączone z A [ ]. Ten wzorzec jest kontynuowany z każdym poziomem rekurencji.

   

     0             
     0     


 // Tablica A[] zawiera elementy do posortowania; tablica B[] jest tablicą roboczą.   void  TopDownMergeSort  (  A  [],  B  [],  n  )  {  CopyArray  (  A  ,  ,  n  ,  B  );  // jednorazowa kopia A[] do B[]  TopDownSplitMerge  (  B  ,  ,  n  ,  A  );  // posortuj dane z B[] do A[]  }  // Podziel A[] na 2 przebiegi, posortuj oba przebiegi do B[], połącz oba przebiegi od B[] do A[] 

    

                              
                                         
    
           // iBegin obejmuje; iEnd jest ekskluzywny (A[iEnd] nie jest w zestawie).   void  TopDownSplitMerge  (  B  [],  iBegin  ,  iEnd  ,  A  [])  {  if  (  iEnd  -  iBegin  <=  1  )  // if run size == 1  return  ;  // uznaj to za posortowane  // podziel ciąg dłuższy niż 1 element na pół  iMiddle  =  (  iEnd  +  iBegin  )  /  2  ;               
    
          
            
    
        // iMiddle = punkt środkowy  // rekurencyjnie posortuj oba przebiegi z tablicy A[] do B[]  TopDownSplitMerge  (  A  ,  iBegin  ,  iMiddle  ,  B  );  // sortowanie lewego biegu  TopDownSplitMerge  (  A  ,  iMiddle  ,  iEnd  ,  B  );  // sortowanie prawego przebiegu  // scalanie wynikowych przebiegów z tablicy B[] do A[]  TopDownMerge  (  B  ,  iBegin  ,  iMiddle  ,  iEnd  ,  





     

         
 
    
        A  );  }  // Lewa połowa źródła to A[ iBegin:iMiddle-1].  // Prawa połowa źródła to A[iMiddle:iEnd-1 ].  // Wynik to B[ iBegin:iEnd-1 ].  void  TopDownMerge  (  A  [],  iBegin  ,  iMiddle  ,  iEnd  ,  B  [])  {  i  =  iBegin  ,  j  =  iMiddle  ;  // Gdy w lewym lub prawym biegu znajdują się elementy...  for  (  k  =  iBegin  ;      
        
                    
              
                 k  <  iKoniec  ;  k  ++  )  {  // Jeśli istnieje lewa głowica biegu i jest <= istniejąca prawa głowica biegu.  if  (  i  <  iŚrodek  &&  (  j  >=  iKoniec  ||  A  [  ja  ]  <=  A  [  j  ]))  {  B  [  k  ]  =  A  [  ja  ];  ja  =  ja  +  1  ; 
          
              
                
        
    


    

           
         }  jeszcze  {  B  [  k  ]  =  ZA  [  j  ];  j  =  j  +  1  ;  }  }  }  void  CopyArray  (  A  [],  iBegin  ,  iEnd  ,  B  [])  {  for  (  k  =  iBegin  ;  k  <  iEnd  ;  k  ++  )  B  [  k  ]   
 =  ZA  [  k  ];  } 

Sortowanie całej tablicy jest realizowane przez TopDownMergeSort(A, B, length(A)) .

Implementacja oddolna

Przykładowy kod podobny do C wykorzystujący indeksy dla algorytmu sortowania przez scalanie od dołu do góry, który traktuje listę jako tablicę n list podrzędnych (zwanych w tym przykładzie przebiegami ) o rozmiarze 1 i iteracyjnie scala listy podrzędne tam iz powrotem między dwoma buforami:

   

    
    
               
     // tablica A[] zawiera elementy do posortowania; tablica B[] jest tablicą roboczą   void  BottomUpMergeSort  (  A  [],  B  [],  n  )  {  // Każdy 1 element uruchomiony w A jest już „posortowany”.  // Wykonuj kolejno dłuższe posortowane serie o długości 2, 4, 8, 16... aż cała tablica zostanie posortowana.  for  (  szerokość  =  1  ;  szerokość  <  n  ;  szerokość  =  2  *  szerokość  )  { 
        
           0          
        
            
            
                 // Tablica A jest pełna ciągów o długości i szerokości.  for  (  i  =  ;  i  <  n  ;  i  =  i  +  2  *  szerokość  )  {  // Połącz dwa przebiegi: A[i:i+width-1] i A[i+width:i+2*width-1] do B[]  // lub skopiuj A[i:n-1] do B[] ( if (i+width >= n) )  BottomUpMerge  (  A  ,  i  ,  min  (  i  +  width  ,  n  ),  min  (  i  +   
        
        
        
        
          
        
    




  2  *  szerokość  ,  n  ),  B  );  }  // Teraz tablica robocza B jest pełna przebiegów o długości 2*width.  // Skopiuj tablicę B do tablicy A dla następnej iteracji.  // Bardziej wydajna implementacja zamieniłaby role A i B.  CopyArray  (  B  ,  A  ,  n  );  // Teraz tablica A jest pełna ciągów o długości 2*width.  }  }  // Lewy bieg to A[iLeft :iRight-1].  // Bieg w prawo to A[iRight:iEnd-1 ].  void  BottomUpMerge  (  A     

         
    
            
        
             [],  iLewa  ,  iPrawa  ,  iKoniec  ,  B  [])  {  ja  =  iLewa  ,  j  =  iPrawa  ;  // Jeśli w lewym lub prawym biegu znajdują się elementy...  for  (  k  =  iLeft  ;  k  <  iEnd  ;  k  ++  )  {  // Jeśli istnieje lewy bieg i jest <= istniejący prawy bieg.  if  (  i  <  iRight  &&         
              
                
          
              
                    
        
     


 (  j  >=  iKoniec  ||  ZA  [  ja  ]  <=  ZA  [  j  ]))  {  b  [  k  ]  =  ZA  [  ja  ];  ja  =  ja  +  1  ;  }  jeszcze  {  B  [  k  ]  =  ZA  [  j  ];  j  =  j  +  1  ;  }  }  }  nieważne    

       0    
          
 CopyArray  (  B  [],  A  [],  n  )  {  for  (  i  =  ;  ja  <  n  ;  i  ++  )  A  [  i  ]  =  B  [  i  ];  } 

Implementacja odgórna przy użyciu list

Pseudokod dla algorytmu sortowania przez scalanie od góry do dołu, który rekurencyjnie dzieli listę wejściową na mniejsze listy podrzędne, dopóki listy podrzędne nie zostaną posortowane w sposób trywialny, a następnie scala listy podrzędne, wracając w górę łańcucha wywołań.

    
        
     function  merge_sort(  list  m)  to  //  przypadek podstawowy. Lista zerowego lub jednego elementu jest z definicji posortowana.   jeśli  długość m ≤ 1  to  zwróć  m //  Przypadek rekurencyjny. Najpierw podziel listę na równej wielkości podlisty   //  składające się z pierwszej i drugiej połowy listy.  //  To zakłada, że ​​listy zaczynają się od indeksu 0.  var  left := pusta lista  var  right := pusta lista  dla każdego  x  z indeksem  i 
         w  m  do  if  i < (długość m)/2  następnie  dodaj x po lewej stronie,  w przeciwnym razie  dodaj x po prawej stronie //  Sortuj rekurencyjnie obie listy podrzędne.  left := merge_sort(left) right := merge_sort(right) // Następnie scalaj posortowane teraz podlisty.  zwróć  scalanie (lewo, prawo) 

W tym przykładzie funkcja scalania łączy lewą i prawą listę podrzędną.

    
        
     funkcja  scalania (lewo, prawo)  to  var  wynik := pusta lista  podczas gdy  lewa nie jest pusta  , a  prawa nie jest pusta  zrób  jeśli  pierwszy (lewy) ≤ pierwszy (prawy)  następnie  dołącz pierwszy (lewy) do wyniku po lewej := reszta (lewa)  w przeciwnym razie  dołącz pierwszy (po prawej) do wyniku po prawej := reszta (po prawej) //  Lewy lub prawy element może mieć pozostawione elementy; je konsumować.   //  (W rzeczywistości zostanie wprowadzona tylko jedna z poniższych pętli.)  while  lewa nie jest pusta  dopisz  pierwszą (z lewej) do wyniku left := reszta (z lewej)  podczas gdy  prawa nie jest pusta  dopisz  pierwszą (z prawej) do wyniku z prawej := reszta (z prawej)  zwróć  wynik 

Implementacja oddolna z wykorzystaniem list

Pseudokod dla algorytmu sortowania przez scalanie od dołu do góry, który wykorzystuje małą tablicę o stałym rozmiarze odwołań do węzłów, gdzie array[i] jest odwołaniem do listy o rozmiarze 2 ⁱ lub nil . węzeł jest odniesieniem lub wskaźnikiem do węzła. Funkcja merge() byłaby podobna do tej pokazanej w przykładzie list scalania od góry do dołu, scala dwie już posortowane listy i obsługuje puste listy. W takim przypadku funkcja merge() użyłaby węzła jako parametrów wejściowych i wartości zwracanej.

             funkcja  merge_sort(  node  head)  to  // zwraca jeśli lista jest pusta  if  head = nil  to  zwraca  nil  var  node  array[32]; początkowo wszystkie nil   var  węzeł  wynik  var  węzeł  następny  var  int  i wynik := głowa // scalanie węzłów w tablicę  while  wynik ≠ nil  do  następny := wynik.następny; wynik.następny := zero   dla  (i = 0; (i < 32) && (tablica[i] ≠ nil); i += 1)  do  wynik := merge(tablica[i], wynik) tablica[i] := zero // nie idź za końcem tablicy  jeśli  i = 32  to  i -= 1 tablica[i] := wynik wynik := następny // scalanie tablicy w pojedynczą listę wynik := zero  dla  (i = 0; i < 32; i += 1)  wykonaj  wynik := merge(tablica[i], wynik)  zwróć  wynik 

Analiza

Rekurencyjny algorytm sortowania przez scalanie używany do sortowania tablicy 7 wartości całkowitych. Oto kroki, które podjąłby człowiek, aby naśladować sortowanie przez scalanie (z góry na dół).

Podczas sortowania n obiektów sortowanie przez scalanie ma średnią i najgorszy przypadek wydajności O ( n log n ) . Jeżeli czas wykonania sortowania przez scalanie dla listy o długości n wynosi T ( n ) , to z definicji algorytmu ( zastosuj algorytm do dwóch listy o połowę mniejsze od oryginalnej listy i dodaj n kroków podjętych w celu połączenia powstałych dwóch list). Zamknięta postać wynika z głównego twierdzenia o nawrotach typu „dziel i zwyciężaj” .

  Liczba porównań wykonanych przez sortowanie przez scalanie w najgorszym przypadku jest określona przez liczby sortujące . Liczby te są równe lub nieco mniejsze niż ( n ⌈ lg n ⌉ − 2 ^{⌈ lg n ⌉} + 1), czyli pomiędzy ( n lg n − n + 1) a ( n lg n + n + O(lg n ) ). Najlepszy przypadek sortowania przez scalanie wymaga o połowę mniej iteracji niż najgorszy przypadek.

Dla dużego n i losowo uporządkowanej listy wejściowej oczekiwana (średnia) liczba porównań sortowania przez scalanie jest o α · n mniejsza niż w najgorszym przypadku, gdzie ${\ Displaystyle \ alfa = -1 + \ suma _ {k = 0} ^ {\ infty} {\ Frac {1} {2 ^ {k} + 1}} \ około 0,2645.}$

W najgorszym przypadku sortowanie przez scalanie wykorzystuje około 39% mniej porównań niż sortowanie szybkie w swoim przeciętnym przypadku, a pod względem ruchów złożoność najgorszego przypadku sortowania przez scalanie wynosi O ( n log n ) - taka sama złożoność jak najlepszy przypadek szybkiego sortowania.

Sortowanie przez scalanie jest bardziej wydajne niż sortowanie szybkie w przypadku niektórych typów list, jeśli do danych, które mają być sortowane, można skutecznie uzyskać dostęp sekwencyjnie, a zatem jest popularne w językach takich jak Lisp , gdzie sekwencyjne struktury danych są bardzo powszechne. W przeciwieństwie do niektórych (wydajnych) implementacji sortowania szybkiego, sortowanie przez scalanie jest sortowaniem stabilnym.

Najpopularniejsza implementacja sortowania przez scalanie nie sortuje w miejscu; dlatego rozmiar pamięci wejściowej musi być przydzielony, aby posortowane dane wyjściowe były przechowywane (patrz poniżej odmiany, które wymagają tylko n /2 dodatkowych spacji).

Naturalne sortowanie przez scalanie

Naturalne sortowanie przez scalanie jest podobne do sortowania przez scalanie od dołu do góry, z wyjątkiem tego, że wykorzystywane są wszystkie naturalnie występujące przebiegi (posortowane sekwencje) na wejściu. Można wykorzystać zarówno przebiegi monotoniczne, jak i bitoniczne (naprzemienne góra/dół), przy czym listy (lub równoważnie taśmy lub pliki) są wygodnymi strukturami danych (używanymi jako kolejki FIFO lub stosy LIFO ). W przypadku sortowania przez scalanie od dołu do góry punkt początkowy zakłada, że ​​każdy przebieg ma długość jednego elementu. W praktyce losowe dane wejściowe będą miały wiele krótkich serii, które po prostu zostaną posortowane. W typowym przypadku naturalne sortowanie przez scalanie może nie wymagać tak wielu przebiegów, ponieważ jest mniej przebiegów do scalenia. W najlepszym przypadku dane wejściowe są już posortowane (tj. są jednym przebiegiem), więc naturalne sortowanie przez scalanie wymaga tylko jednego przejścia przez dane. W wielu praktycznych przypadkach występują długie naturalne przebiegi iz tego powodu naturalne sortowanie przez scalanie jest wykorzystywane jako kluczowy składnik Timsort . Przykład:

Start : 3 4 2 1 7 5 8 9 0 6 Wybierz przebiegi : (3 4)(2)(1 7)(5 8 9)(0 6) Połącz : (2 3 4)(1 5 7 8 9)( 0 6) Połącz: (1 2 3 4 5 7 8 9)(0 6) Połącz: (0 1 2 3 4 5 6 7 8 9)

Formalnie mówi się, że naturalne sortowanie przez scalanie jest optymalne dla przebiegów, gdzie $to$$\ Displaystyle {\ mathtt {przebiegi}} (L)}$ liczba przebiegów w minus jeden.

Sortowanie z zamianą turniejów służy do zbierania początkowych przebiegów dla zewnętrznych algorytmów sortowania.

Sortowanie przez scalanie w ping-ponga

Zamiast łączenia dwóch bloków na raz, ping-pong łączy cztery bloki na raz. Cztery posortowane bloki są jednocześnie łączone z przestrzenią pomocniczą w dwa posortowane bloki, a następnie dwa posortowane bloki są ponownie łączone z pamięcią główną. W ten sposób pomija się operację kopiowania i zmniejsza całkowitą liczbę ruchów o połowę. Wczesna implementacja łączenia czterech na raz w domenie publicznej została przeprowadzona przez WikiSort w 2014 r., Metoda ta została później opisana jako optymalizacja sortowania cierpliwości i nazwana łączeniem ping-ponga. Quadsort wdrożył tę metodę w 2020 roku i nazwał ją łączeniem poczwórnym.

Sortowanie przez scalanie na miejscu

Jedną wadą sortowania przez scalanie, gdy jest zaimplementowane na tablicach, jest zapotrzebowanie na pamięć roboczą O ( n ) . Zaproponowano kilka metod zmniejszenia pamięci lub pełnego sortowania przez scalanie :

• Kronrod (1969) zaproponował alternatywną wersję sortowania przez scalanie, która wykorzystuje stałą dodatkową przestrzeń.
• Katajainen i in. przedstaw algorytm, który wymaga stałej ilości pamięci roboczej: wystarczającej ilości miejsca do przechowywania jednego elementu tablicy wejściowej i dodatkowej przestrzeni do przechowywania wskaźników O (1) do tablicy wejściowej. Osiągają O ( n log n ) związany z małymi stałymi, ale ich algorytm nie jest stabilny.
• Podjęto kilka prób stworzenia algorytmu scalania w miejscu , który można połączyć ze standardowym sortowaniem przez scalanie (od góry do dołu lub od dołu do góry) w celu utworzenia sortowania przez scalanie na miejscu. W tym przypadku pojęcie „w miejscu” można złagodzić, oznaczając „zajmowanie logarytmicznej przestrzeni stosu”, ponieważ standardowe sortowanie przez scalanie wymaga takiej ilości miejsca do własnego wykorzystania stosu. Wykazali to Geffert i in. że stabilne łączenie w miejscu jest możliwe w O ( n log n ) czas przy użyciu stałej ilości miejsca na zarysowania, ale ich algorytm jest skomplikowany i ma wysokie stałe współczynniki: łączenie tablic o długości n i m może zająć 5 n + 12 m + o ( m ) ruchów. Ten wysoki stały współczynnik i skomplikowany algorytm w miejscu zostały uproszczone i łatwiejsze do zrozumienia. Bing-Chao Huang i Michael A. Langston przedstawili prosty liniowy algorytm czasu, który umożliwia praktyczne łączenie w miejscu scalić posortowaną listę przy użyciu ustalonej ilości dodatkowej przestrzeni. Obaj korzystali z prac Kronroda i innych. Łączy się w czasie liniowym i stałej dodatkowej przestrzeni. Algorytm zajmuje niewiele więcej średniego czasu niż standardowe algorytmy sortowania przez scalanie, swobodnie wykorzystując O (n) tymczasowych dodatkowych komórek pamięci, mniej niż dwukrotnie. Chociaż algorytm jest znacznie szybszy w praktyczny sposób, ale jest niestabilny również dla niektórych list. Ale stosując podobne koncepcje, udało im się rozwiązać ten problem. Inne algorytmy działające w miejscu obejmują SymMerge, który przyjmuje O (( n + m ) log ( n + m )) czas w sumie i jest stabilny. Podłączenie takiego algorytmu do sortowania przez scalanie zwiększa jego złożoność do nieliniowej , ale wciąż quasiliniowej , O ( n (log n ) ² ) .
• Wiele aplikacji sortowania zewnętrznego wykorzystuje formę sortowania przez scalanie, w której dane wejściowe są dzielone na większą liczbę list podrzędnych, najlepiej do liczby, dla której ich scalanie nadal sprawia, że ​​aktualnie przetwarzany zestaw stron mieści się w pamięci głównej.
• Nowoczesnym stabilnym wariantem scalania liniowego i miejscowego jest sortowanie przez scalanie bloków , które tworzy sekcję unikalnych wartości do wykorzystania jako przestrzeń wymiany.
• Narzut przestrzeni można zredukować do sqrt( n ) za pomocą wyszukiwania binarnego i rotacji. Ta metoda jest wykorzystywana przez bibliotekę C++ STL i quadsort.
• Alternatywą dla ograniczenia kopiowania do wielu list jest powiązanie nowego pola informacji z każdym kluczem (elementy w m nazywane są kluczami). To pole będzie używane do łączenia kluczy i wszelkich powiązanych informacji w posortowaną listę (klucz i powiązane z nim informacje nazywane są rekordem). Następnie scalanie posortowanych list odbywa się poprzez zmianę wartości łącza; żadne rekordy nie muszą być w ogóle przenoszone. Pole, które zawiera tylko łącze, będzie na ogół mniejsze niż cały rekord, więc zajmie mniej miejsca. Jest to standardowa technika sortowania, nieograniczona do sortowania przez scalanie.
• Prostym sposobem na zmniejszenie narzutu miejsca do n /2 jest zachowanie lewej i prawej strony jako połączonej struktury, skopiowanie tylko lewej części m do tymczasowej przestrzeni i skierowanie procedury scalającej tak, aby umieściła scalone dane wyjściowe w m . W tej wersji lepiej jest alokować tymczasową przestrzeń poza scalania , tak aby potrzebna była tylko jedna alokacja. Wspomniane wcześniej nadmierne kopiowanie jest również łagodzone, ponieważ ostatnia para linii przed zwróceniem wyniku instrukcja ( scalanie funkcji w powyższym pseudokodzie) staje się zbędna.

Używaj z napędami taśmowymi

Algorytmy sortowania przez scalanie umożliwiały sortowanie dużych zestawów danych na wczesnych komputerach, które miały małe pamięci o dostępie swobodnym według nowoczesnych standardów. Zapisy były przechowywane na taśmie magnetycznej i przetwarzane na bankach napędów taśmowych, takich jak IBM 729 .

Zewnętrzne sortowanie przez scalanie jest praktyczne przy użyciu dysków lub napędów taśmowych , gdy dane do sortowania są zbyt duże, aby zmieściły się w pamięci . Sortowanie zewnętrzne wyjaśnia sposób implementacji sortowania przez scalanie z dyskami. Typowe sortowanie napędu taśmowego wykorzystuje cztery napędy taśmowe. Wszystkie wejścia/wyjścia są sekwencyjne (z wyjątkiem przewijania do tyłu na końcu każdego przebiegu). Minimalna implementacja może obejść się przy użyciu zaledwie dwóch buforów rekordów i kilku zmiennych programu.

Nazywając cztery napędy taśmowe A, B, C, D, z oryginalnymi danymi w A i używając tylko dwóch buforów rekordów, algorytm jest podobny do implementacji oddolnej , wykorzystującej pary napędów taśmowych zamiast macierzy w pamięci. Podstawowy algorytm można opisać następująco:

1. Połącz pary rekordów z A; zapisywanie dwurekordowych list podrzędnych naprzemiennie do C i D.
2. Połącz listy podrzędne z dwoma rekordami z C i D w listy podrzędne z czterema rekordami; pisząc je na przemian do A i B.
3. Połącz listy podrzędne z czterema rekordami z A i B w listy podrzędne z ośmioma rekordami; pisząc je na przemian do C i D
4. Powtarzaj, aż uzyskasz jedną listę zawierającą wszystkie posortowane dane — w dzienniku ₂ ( n ) przechodzi.

Zamiast zaczynać od bardzo krótkich przebiegów, zwykle stosuje się algorytm hybrydowy , w którym początkowy przebieg wczytuje wiele rekordów do pamięci, przeprowadza wewnętrzne sortowanie w celu utworzenia długiego przebiegu, a następnie rozdziela te długie przebiegi na zestaw wyjściowy. Krok pozwala uniknąć wielu wczesnych podań. Na przykład wewnętrzne sortowanie 1024 rekordów pozwoli zaoszczędzić dziewięć przebiegów. Sortowanie wewnętrzne jest często duże, ponieważ ma taką zaletę. W rzeczywistości istnieją techniki, które mogą sprawić, że początkowe przebiegi będą dłuższe niż dostępna pamięć wewnętrzna. Jeden z nich, „pług śnieżny” Knutha (oparty na binarnym min-heap ), generuje przebiegi dwa razy dłuższe (średnio) niż rozmiar używanej pamięci.

Przy pewnym obciążeniu powyższy algorytm można zmodyfikować tak, aby korzystał z trzech taśm. Czas działania O ( n log n ) można również osiągnąć za pomocą dwóch kolejek lub stosu i kolejki lub trzech stosów. W przeciwnym kierunku, używając k > dwóch taśm (i O ( k ) elementów w pamięci), możemy zmniejszyć liczbę operacji na taśmach w O (log k ) razy, używając k/2-kierunkowego scalania .

Bardziej wyrafinowanym sortowaniem przez scalanie, które optymalizuje użycie napędu taśmowego (i dysku), jest sortowanie przez scalanie wielofazowe .

Optymalizacja sortowania przez scalanie

Sortowanie kafelkowe przez scalanie zastosowane do tablicy losowych liczb całkowitych. Oś pozioma to indeks tablicy, a oś pionowa to liczba całkowita.

Na nowoczesnych komputerach lokalizacja odniesienia może mieć ogromne znaczenie w optymalizacji oprogramowania , ponieważ stosowane są wielopoziomowe hierarchie pamięci . Zaproponowano wersje algorytmu sortowania przez scalanie uwzględniające pamięć podręczną, których operacje zostały specjalnie wybrane, aby zminimalizować ruch stron do iz pamięci podręcznej maszyny . Na przykład algorytm sortowania kafelkowego przez scalanie zatrzymuje partycjonowanie podtablic po osiągnięciu podtablic o rozmiarze S, gdzie S to liczba elementów danych mieszczących się w pamięci podręcznej procesora. Każda z tych podtablic jest sortowana za pomocą algorytmu sortowania w miejscu, takiego jak sortowanie przez wstawianie , aby zniechęcić do zamiany pamięci, a następnie normalne sortowanie przez scalanie jest wykonywane w standardowy sposób rekurencyjny. Ten algorytm wykazał lepszą wydajność na komputerach, które korzystają z optymalizacji pamięci podręcznej. ( LaMarca i Ladner 1997 )

Sortowanie przez scalanie równoległe

Sortowanie przez scalanie jest dobrze zrównoleglone dzięki zastosowaniu metody dziel i zwyciężaj . Na przestrzeni lat opracowano kilka różnych równoległych wariantów algorytmu. Niektóre algorytmy sortowania równoległego przez scalanie są silnie powiązane z sekwencyjnym algorytmem scalania odgórnego, podczas gdy inne mają inną ogólną strukturę i wykorzystują metodę scalania K-way .

Sortowanie przez scalanie z rekurencją równoległą

Procedurę sekwencyjnego sortowania przez scalanie można opisać w dwóch fazach, fazie dzielenia i fazie scalania. Pierwszy składa się z wielu wywołań rekurencyjnych, które wielokrotnie wykonują ten sam proces dzielenia, aż podsekwencje zostaną trywialnie posortowane (zawierają jeden element lub nie zawierają żadnego elementu). Intuicyjnym podejściem jest zrównoleglenie tych wywołań rekurencyjnych. Poniższy pseudokod opisuje sortowanie przez scalanie z rekurencją równoległą przy użyciu fork i join :

     //  Sortuj elementy od lo do hi (wyłącznie) tablicy A.  algorytm  mergesort(A, lo, hi)  to  if  lo+1 < hi  then  //  Dwa lub więcej elementów.  mid := ⌊(lo + hi) / 2⌋  rozwidlenie  mergesort(A, lo, mid) mergesort(A, mid, hi)  join  merge(A, lo, mid, hi) 

Algorytm ten jest trywialną modyfikacją wersji sekwencyjnej i nie jest dobrze zrównoleglany. Dlatego jego przyspieszenie nie jest zbyt imponujące. Ma rozpiętość , co $\ Displaystyle \ Theta (\ log n)}$ jedynie ulepszeniem $n )$ z sekwencyjną ( Wprowadzenie do algorytmów ). Wynika to głównie z metody łączenia sekwencyjnego, ponieważ jest wąskim gardłem równoległych wykonań.

Sortowanie przez scalanie z łączeniem równoległym

Główny artykuł: Algorytm scalania § Łączenie równoległe

Lepszą równoległość można osiągnąć za pomocą algorytmu łączenia równoległego . Cormen i in. przedstawić wariant binarny, który łączy dwie posortowane podsekwencje w jedną posortowaną sekwencję wyjściową.

W jednym z ciągów (dłuższym przy nierównej długości) wybierany jest element o środkowym indeksie. Jego pozycja w drugiej sekwencji jest określana w taki sposób, że ta sekwencja pozostanie posortowana, jeśli ten element zostanie wstawiony w tym miejscu. Dzięki temu wiadomo, ile innych elementów z obu ciągów jest mniejszych i można obliczyć pozycję wybranego elementu w ciągu wyjściowym. Dla utworzonych w ten sposób częściowych sekwencji mniejszych i większych elementów algorytm scalania jest ponownie wykonywany równolegle, aż do osiągnięcia przypadku bazowego rekurencji.

Poniższy pseudokod pokazuje zmodyfikowaną metodę równoległego sortowania przez scalanie przy użyciu algorytmu równoległego scalania (przejętego z Cormen i in.).

 /** * A: tablica wejściowa * B: tablica wyjściowa * lo: dolna granica * hi: górna granica * off: przesunięcie */  algorytm  parallelMergesort(A, lo, hi, B, off)  to  len := hi - lo + 1  jeśli  len == 1  to  B[off] := A[lo]  w przeciwnym razie  niech T[1..len] będzie nową tablicą mid := ⌊(lo + hi) / 2⌋ mid' := mid - lo + 1  widelec  równoległyMergesort(A, lo, mid, T, 1) równoległyMergesort(A, mid + 1, hi, T, mid' + 1) join parallelMerge(  T  , 1, mid', mid' + 1, len, B, wyłączony) 

Aby przeanalizować relację rekurencyjną dla rozpiętości najgorszego przypadku, wywołania rekurencyjne funkcji parallelMergesort muszą być włączone tylko raz ze względu na ich równoległe wykonanie, uzyskując

$${\ Displaystyle T _ {\ infty} ^ {\ text {sort}} (n) = T _ {\ infty} ^ {\ text {sort}} \ lewo ({\ Frac {n} {2}} \ right) + T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+\Theta \ lewo(\log(n)^{2}\prawo).}$$

Aby uzyskać szczegółowe informacje na temat złożoności procedury scalania równoległego, zobacz Algorytm scalania .

Rozwiązanie tego nawrotu jest podane przez

$${\ Displaystyle T _ {\ infty} ^ {\ tekst {sort}} = \ Theta \ lewo (\ log (n) ^ {3} \ prawo).}$$

$_$ równoległość _ jest znacznie wyższy niż równoległość poprzedniego algorytmu. Takie sortowanie może dobrze działać w praktyce w połączeniu z szybkim, stabilnym sortowaniem sekwencyjnym, takim jak sortowanie przez wstawianie , oraz szybkim łączeniem sekwencyjnym jako podstawowym przypadkiem łączenia małych tablic.

Równoległe sortowanie wielokierunkowe przez scalanie

Ograniczenie algorytmów sortowania przez scalanie do metody scalania binarnego wydaje się arbitralne, ponieważ zwykle dostępne są procesory p > 2. Lepszym podejściem może być użycie scalania w sposób K , uogólnienia scalania binarnego, w którym $posortowane$ sekwencje. Ten wariant scalania dobrze nadaje się do opisania algorytmu sortowania w PRAM .

Podstawowy pomysł

Równoległy wielokierunkowy proces scalania na czterech procesorach ${\ displaystyle t_ {0}}$ do ${\ displaystyle t_ {3}}$ .

$dostępnymi$ pod uwagę $elementów$ sekwencję , celem jest posortowanie sekwencji z procesorami . Elementy te są rozdzielane równo między wszystkie procesory i sortowane lokalnie przy użyciu algorytmu sortowania sekwencyjnego . Zatem ciąg składa się z posortowanych ciągów $Displaystyle S_ {1}, ..., S_ {p}}$ ⌈ ${\ textstyle \ lceil {\ frac {n}{p}} \ rceil}$ . Dla uproszczenia niech ${\ displaystyle n}$ będzie wielokrotnością ${\ displaystyle p}$ tak, że ${\textstyle \left\vert S_ {i}\right\vert = {\frac {n}{p}}}$ dla $, p}$ .

Sekwencje te zostaną użyte do przeprowadzenia selekcji wielosekwencji/wyboru rozdzielania. dla ${\ Displaystyle j = 1, ..., p}$ algorytm określa elementy rozdzielające ${\ Displaystyle v_ {j}}$ z globalną rangą ${\ textstyle k = j {\ frac {n }{p}}}$ . Następnie odpowiednie pozycje $p$$}$ w każdej sekwencji określane za pomocą wyszukiwania binarnego , a zatem są dalej ${\ displaystyle S_ {i}}$${\ Displaystyle S_ {i, 1}, ..., S_ {i, p}}$ na $podsekwencje$ _ z ${\ textstyle S_ {i, j}: = \ {x \ w S_ {i} | ranga (v_{j-1})<ranking(x)\leq rank(v_{j})\}}$ .

Ponadto elementy ${\ Displaystyle S_ {1, i}, ..., S_ {p, i}}$ są przypisane do procesora ${\ Displaystyle i}$ , oznacza wszystkie elementy między rangą ${ \textstyle (i-1){\frac {n}{p}}}$ i rank ${\textstyle i{\frac {n}{p}}}$ , które są rozłożone na wszystkie ${\ Displaystyle S_ {i}}$ . W ten sposób każdy procesor otrzymuje sekwencję posortowanych sekwencji. Fakt, że ranga $została wybrana globalnie,$ rozdzielacza $k$ z jednej strony wybrano tak, że każdy $\ displaystyle k}$ procesor może nadal działać na elementach ${\textstyle n/p}$ po przypisaniu. Algorytm jest doskonale zrównoważony pod względem obciążenia . Z drugiej strony wszystkie elementy na procesorze ${\ displaystyle i}$ są mniejsze lub równe wszystkim elementom procesora ${\ displaystyle i + 1}$ . W związku z tym każdy procesor wykonuje scalanie p - way iw ten sposób uzyskuje posortowaną sekwencję ze swoich podsekwencji. Ze względu na drugą właściwość nie ma potrzeby przeprowadzania dalszego p -way-merge, wyniki muszą być jedynie połączone w kolejności numerów procesorów.

Wybór wielu sekwencji

W najprostszej postaci, biorąc pod $posortowane$ sekwencje ${1}, ..., S_ {p}}$${\ displaystyle k}$ równomiernie rozłożone na $k$ i rangi , zadaniem jest znalezienie elementu ${\ displaystyle k} displaystyle x}$ z globalną rangą $połączeniu$ sekwencji. związku z tym można tego użyć do podzielenia każdego ${\ Displaystyle S_ {i}} na dwie części$$displaystyle$ indeksie rozdzielacza gdzie dolna część zawiera tylko elementy mniejsze niż $x}$ , podczas gdy elementy większe niż ${\ displaystyle x}$ znajdują się w górnej części.

Przedstawiony algorytm sekwencyjny zwraca indeksy podziałów w każdej sekwencji, np. indeksy $displaystyle S_ {i$ sekwencjach takie, że $] {\ displaystyle$$}$ ma globalną rangę mniejszą niż ${\ displaystyle k}$ i ${\ Displaystyle \ operatorname {ranga} \ lewo (S_ {i} [l_ {i} + 1] \ prawej) \ geq k}$ .

     algorytm  msSelect(S : Tablica posortowanych Sekwencji [S_1,..,S_p], k : int)  jest  dla  i = 1  do  p  do  (l_i, r_i) = (0, |S_i|-1)  dopóki  istnieje i: l_i < r_i  do  // wybierz element Pivot w S_j[l_j], .., S_j[r_j], jednolicie wybierz losowe j v := pickPivot(S, l, r) for  i  = 1  to  p  do  m_i = binarySearch(v , S_i[l_i, r_i]) // sekwencyjnie  jeśli  m_1 + ... + m_p >= k  to  // m_1+ ... + m_p jest globalną rangą v r := m // przypisanie wektora  else  l := m  return  l 

Do analizy złożoności wybrano model PRAM . Jeśli dane są równomiernie rozłożone we wszystkich $binarySearch$ p-krotne wykonanie metody ma czas działania $\ displaystyle {\ mathcal {O}} \left(p\log \left(n/p\right)\right)}$ { . Oczekiwana głębokość rekurencji to ${\ Displaystyle {\ mathcal {O}} \ lewo (\ log \ lewo (\ textstyle \ suma _ {i} | S_ {i} | \ prawej) \ prawej) = {\mathcal {O}}(\log(n))}$ jak w zwykłym Quickselect . Zatem całkowity oczekiwany czas działania wynosi ${\ Displaystyle {\ mathcal {O}} \ lewo (p \ log (n/p) \ log (n) \ prawo)}$ .

Zastosowany w równoległym wielokierunkowym sortowaniu przez scalanie algorytm ten musi być wywoływany równolegle tak, aby wszystkie elementy rozdzielające rangi ${\ textstyle i {\ frac {n} {p}}}$ dla ${\ Displaystyle i = 1, ..., p}$ się jednocześnie. Te elementy rozdzielacza można następnie wykorzystać do podzielenia każdej sekwencji na $,$ z tym samym całkowitym czasem działania ${\ Displaystyle {\ mathcal {O}} \ lewo (p \ \ log (n/p) \ log (n) \ prawo)}$ .

Pseudo kod

Poniżej podano pełny pseudokod algorytmu równoległego sortowania wielokierunkowego przez scalanie. Zakładamy, że istnieje synchronizacja barierowa przed i po selekcji multisekwencji, tak że każdy procesor może prawidłowo określić elementy podziału i podział sekwencji.

 /** * d: nieposortowana tablica elementów * n: liczba elementów * p: liczba procesorów * return posortowana tablica */ algorytm  parallelMultiwayMergesort  (d : tablica, n : int, p : int)  is  o :=  nowa  tablica[ 0, n] // tablica wyjściowa  dla  i = 1  do  p  wykonaj równolegle  // każdy procesor równolegle S_i := d[(i-1) * n/p, i * n/p] // Sekwencja długości n/p sort(S_i) // sortuj lokalnie  synchronizuj  v_i := msSelect([S_1,...,S_p], i * n/p) // element o randze globalnej i * n/p  synch  (S_i,1, ..., S_i,p) := sequence_partitioning( si, v_1, ..., v_p) // podziel s_i na podsekwencje o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i) // scalanie i przypisywanie do tablicy wyjściowej  return  o 

Analiza

$(n/p\;\log(n/p)\right)}$$sortuje$ przypisane elementy lokalnie przy użyciu algorytmu sortowania o złożoności $\ Displaystyle {\ mathcal {O}} \$ . Następnie należy obliczyć elementy rozdzielacza w czasie ${\ Displaystyle {\ mathcal {O}} \ lewo (p \, \ log (n/p) \ log (n) \ prawo)}$ . Wreszcie, $podziałów$ grupa musi być połączona równolegle przez każdy procesor z czasem działania ${\ Displaystyle {\ mathcal {O}} (\ log (p)\;n/p)}$ przy użyciu algorytmu sekwencyjnego łączenia p-kierunkowego . Zatem całkowity czas działania jest określony przez

${\ Displaystyle {\ mathcal {O}} \ lewo ({\ Frac {n }{p}}\log \left({\frac {n}{p}}\right)+p\log \left({\frac {n}{p}}\right)\log(n)+{ \frac {n}{p}}\log(p)\right)}$ .

Praktyczna adaptacja i zastosowanie

Algorytm wielokierunkowego sortowania przez scalanie jest bardzo skalowalny dzięki wysokim możliwościom równoległości, co pozwala na użycie wielu procesorów. To sprawia, że ​​algorytm jest realnym kandydatem do sortowania dużych ilości danych, takich jak przetwarzane w klastrach komputerowych . Ponadto, ponieważ w takich systemach pamięć zwykle nie jest zasobem ograniczającym, wada złożoności przestrzennej sortowania przez scalanie jest pomijalna. Jednak w takich systemach ważne stają się inne czynniki, których nie bierze się pod uwagę przy modelowaniu na PRAM . Tutaj należy wziąć pod uwagę następujące aspekty: Hierarchia pamięci , gdy dane nie mieszczą się w pamięci podręcznej procesorów, lub obciążenie komunikacyjne związane z wymianą danych między procesorami, co może stać się wąskim gardłem, gdy dostęp do danych nie będzie już możliwy za pośrednictwem pamięci współdzielonej.

Sanders i in. przedstawili w swoim artykule $displaystyle$ synchroniczny algorytm równoległy dla wielopoziomowego wielokierunkowego scalania, który dzieli procesory na grupy o rozmiarze $p$$'$ . Wszystkie procesory najpierw sortują lokalnie. W przeciwieństwie do jednopoziomowego sortowania wielokierunkowego, sekwencje te są następnie dzielone na ${\ displaystyle r}$ części i przypisane do odpowiednich grup procesorów. Te kroki są powtarzane rekurencyjnie w tych grupach. Zmniejsza to komunikację, a zwłaszcza pozwala uniknąć problemów z wieloma małymi wiadomościami. Hierarchiczna struktura podstawowej sieci rzeczywistej może być wykorzystana do zdefiniowania grup procesorów (np. szafy , klastry ,...).

Dalsze warianty

Sortowanie przez scalanie było jednym z pierwszych algorytmów sortowania, w którym osiągnięto optymalne przyspieszenie, a Richard Cole użył sprytnego algorytmu podpróbkowania, aby zapewnić scalanie O (1). Inne wyrafinowane algorytmy sortowania równoległego mogą osiągnąć takie same lub lepsze ograniczenia czasowe przy niższej stałej. Na przykład w 1991 roku David Powers opisał równoległe sortowanie szybkie (i pokrewne sortowanie radix ), które może działać w czasie O (log n ) na równoległej maszynie o dostępie swobodnym (PRAM) CRCW z n procesorów poprzez niejawne partycjonowanie. Powers dalej pokazuje, że potokowa wersja Bitonic Mergesort Batchera w czasie O ((log n ) ^{2 ) w} sieci sortowania motyli jest w rzeczywistości szybsza niż jego sortowanie O (log n ) w PRAM, i zapewnia szczegółowe omówienie ukryte koszty ogólne w porównaniu, sortowaniu podstawowym i równoległym.

Porównanie z innymi algorytmami sortowania

Chociaż sortowanie na stosie ma takie same ograniczenia czasowe jak sortowanie przez scalanie, wymaga tylko przestrzeni pomocniczej Θ(1) zamiast Θ( n ) sortowania przez scalanie. W typowych nowoczesnych architekturach wydajne szybkiego sortowania generalnie przewyższają sortowanie przez scalanie w przypadku sortowania tablic opartych na pamięci RAM. Z drugiej strony, sortowanie przez scalanie jest sortowaniem stabilnym i bardziej wydajnym w obsłudze multimediów sekwencyjnych o wolnym dostępie. Sortowanie przez scalanie jest często najlepszym wyborem do sortowania połączonej listy : w tej sytuacji stosunkowo łatwo jest zaimplementować sortowanie przez scalanie w taki sposób, aby wymagało tylko Θ(1) dodatkowej przestrzeni, a niska wydajność dostępu swobodnego połączonej listy sprawia, że ​​niektóre inne algorytmy (takie jak szybkie sortowanie) działają słabo , a inne (jak heapsort) zupełnie niemożliwe.

Począwszy od Perla 5.8, domyślnym algorytmem sortowania jest sortowanie przez scalanie (w poprzednich wersjach Perla było to sortowanie szybkie). W języku Java metody Arrays.sort () wykorzystują sortowanie przez scalanie lub dostrojone sortowanie szybkie w zależności od typów danych, a w celu zwiększenia wydajności implementacji przełącza się na sortowanie przez wstawianie , gdy sortowanych jest mniej niż siedem elementów tablicy. Jądro Linuksa używa sortowania przez scalanie dla swoich połączonych list. Python używa Timsort , innej dostrojonej hybrydy sortowania przez scalanie i sortowanie przez wstawianie, która stała się standardowym algorytmem sortowania w Javie SE 7 (dla tablic typów nieprymitywnych), na platformie Android oraz w GNU Octave .

Notatki

•   Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Wprowadzenie do algorytmów (wyd. 3). MIT Press i McGraw-Hill. ISBN 0-262-03384-4 .
•    Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). „Praktyczne sortowanie na miejscu” . Nordic Journal of Computing . 3 (1): 27–40. CiteSeerX 10.1.1.22.8523 . ISSN 1236-6064 . Zarchiwizowane od oryginału w dniu 2011-08-07 . Źródło 2009-04-04 . . Również praktyczne sortowanie scalone na miejscu . Również [3]
•   Knuth, Donald (1998). „Sekcja 5.2.4: Sortowanie przez scalanie” . Sortowanie i wyszukiwanie . Sztuka programowania komputerowego . Tom. 3 (wyd. 2). Addison-Wesley. s. 158–168. ISBN 0-201-89685-0 .
• Kronrod, MA (1969). „Algorytm optymalnego porządkowania bez pola operacyjnego”. Matematyka radziecka - Doklady . 10 : 744.
•   LaMarca, A.; Ladner, RE (1997). „Wpływ pamięci podręcznych na wydajność sortowania”. proc. 8 Ann. ACM-SIAM Symp. O algorytmach dyskretnych (SODA97) : 370–379. CiteSeerX 10.1.1.31.1153 .
•   Skiena, Steven S. (2008). „4.5: Sortowanie przez scalanie: sortowanie według zasady dziel i zwyciężaj” . Podręcznik projektowania algorytmów (wyd. 2). Skoczek. s. 120–125. ISBN 978-1-84800-069-8 .
• Mikrosystemy Słońca. „Interfejs API tablic (Java SE 6)” . Źródło 2007-11-19 .
• Oracle Corp. „Tablice (Java SE 10 i JDK 10)” . Źródło 2018-07-23 .

Linki zewnętrzne

• Animowane algorytmy sortowania: sortowanie przez scalanie w Wayback Machine (archiwum 6 marca 2015 r.) - demonstracja graficzna
• Otwarte struktury danych — sekcja 11.1.1 — sortowanie przez scalanie , Pat Morin