Z Wikipedii

Sortowanie przez scalanie

W informatyce sortowanie przez scalanie (ang. merge sort), to rekurencyjny algorytm sortowania danych.

Algorytm ten jest dobrym przykładem algorytmów typu Dziel i zwyciężaj (ang. divide and conquer). Ideą działania tego typu algorytmów jest podział problemu na mniejsze części, których rozwiązanie jest już łatwiejsze. Odkrycie algorytmu przypisuje się Johnowi von Neumannowi.

Wyróżnić można trzy podstawowe kroki:

1. Podziel zestaw danych na dwie, równe części (w przypadku nieparzystej liczby wyrazów jedna część będzie o 1 wyraz dłuższa);
2. Zastosuj sortowanie przez scalanie dla każdej z nich oddzielnie, chyba że pozostał już tylko jeden element;
3. Połącz posortowane podciągi w jeden.

Procedura scalania dwóch ciągów A[1..n] i B[1..m] do ciągu C[1..m+n]:

1. Utwórz wskaźniki na początki ciągów A i B -> i=0, j=0
2. Jeżeli A[i] < = B[j] wstaw A[i] do C i zwiększ i o jeden, w przeciwnym przypadku wstaw B[j] do C i zwiększ j o jeden
3. Powtarzaj krok 2 aż wszystkie wyrazy A i B trafią do C

Scalenie wymaga O(n+m) operacji porównań elementów i wstawienia ich do tablicy wynikowej.

[edytuj] Złożoność czasowa algorytmu sortowania przez scalanie

Sortowanie przez scalanie zastosowane do tablicy 7-elementowej.

Bez straty ogólności załóżmy, że długość ciągu, który mamy posortować jest potęgą 2ki (patrz Złożoność obliczeniowa)

Obrazek obok przedstawia drzewo rekursji wywołania algorytmu mergesort, wartości po prawej oznaczają czas wykonania każdego poziomu.

Mamy wiÄ™c drzewo o gÅ‚Ä™bokoÅ›ci log₂ n, na każdym poziomie dokonujemy scalenia o Å‚Ä…cznym koszcie nxc, gdzie c jest staÅ‚Ä… zależnÄ… od komputera. A wiÄ™c intuicyjnie, tzn. nieformalnie możemy dowieść, że zÅ‚ożoność algorytmu mergesort to log₂ n x n

Formalnie złożoność czasową sortowania przez scalanie możemy przedstawić następująco:

T(1) = O(1)

Ciągi jednoelementowe możemy posortować w czasie stałym, czas sortowania ciągu n elementowego to scalenie dwóch ciągów elementowych ( czyli 0(n)) , plus czas potrzebny na posortowanie dwóch, o połowę mniejszych ciągów.

Mamy:

gdzie n = 2^k

Po rozwinięciu nawiasów otrzymamy:

T(n) = 2nlogn

A więc asymptotyczny czas sortowania przez scalanie wynosi O(n log n) (zobacz: notacja dużego O).

[edytuj] Dowód poprawności algorytmu sortowania przez scalanie

Dowód przez indukcję względem długości n tablicy elementów do posortowania.

1) n=2

Algorytm podzieli dane wejściowe na dwie części, po czym zastosuje dla nich scalanie do posortowanej tablicy

2) Zał.: dla ciągów długości k, k<n algorytm mergesort prawidłowo sortuje owe ciągi.

Dla ciągu długości n algorytm podzieli ten ciąg na dwa ciągi długości n/2. Na mocy założenia indukcyjnego ciągi te zostaną prawidłowo podzielone i scalone do dwóch posortowanych ciągów długości n/2. Ciągi te zostaną natomiast scalone przez procedurę scalającą do jednego, posortowanego ciągu długości n.

[edytuj] Przykład kodu źródłowego

Język: SML

fun merge l [] = l
  | merge [] r = r
  | merge (l as x::xs) (r as y::ys) = if x < y then x::merge xs r  
                                      else y::merge l ys;

fun odd  [] = [] | odd  (x::xs) = even xs
and even [] = [] | even (x::xs) = x::odd xs;

fun mergesort []  = []
  | mergesort [x] = [x]
  | mergesort l   = merge (mergesort (odd l)) (mergesort (even l));

Język: Haskell

merge [] xs = xs
merge x [] = x
merge (x:xs) (y:ys) = if x <= y
                      then x : merge xs (y:ys)
                      else y : merge (x:xs) ys

mergesort [] = []
mergesort [x] = [x]
mergesort xs = let (as, bs) = splitAt (length xs `quot` 2) xs
               in merge (mergesort as) (mergesort bs)

Język: C

 /*
  * Sortowanie liczb (typ ustawiany wewnątrz kodu źródłowego).
  */
 
 #include <stdio.h>
 #include <stdlib.h>
 
 typedef unsigned int TYP;
 #define OZNACZENIE_TYPU "u"
 // oznaczenie odpowiednio do printf(3) i TYPu
 
 TYP *tablica;
 
 void merge(unsigned long start, unsigned long srodek, unsigned long stop)
 {
   TYP tab_out[stop-start+1];
   unsigned long i1, i2, io, k;
   i1 = start;
   i2 = srodek+1;
   io = 0;
   while ((i1 <= srodek) && (i2 <= stop))
     if (tablica[i1] < tablica[i2])
       tab_out[io++] = tablica[i1++];
     else
       tab_out[io++] = tablica[i2++];
   if (i1 > srodek)
     for (k = i2; k <= stop; k++, io++)
       tab_out[io] = tablica[k];
   else
     for (k = i1; k <= srodek; k++, io++)
       tab_out[io] = tablica[k];
   for (k = start; k <= stop; k++)
     tablica[k] = tab_out[k-start];
 }
 
 void merge_sort(unsigned long start, unsigned long stop)
 {
   if (start == stop) return;
   else
   {
     unsigned long srodek = (start+stop)/2;
     merge_sort(start, srodek);
     merge_sort(srodek+1, stop);
     merge(start, srodek, stop);
   }
 }
 
 unsigned long i, licznik = 0;
 
 TYP in = 0;
 char *smiec;
 
 int main(void)
 {
   while (!feof(stdin))
     if (fscanf(stdin, "%" OZNACZENIE_TYPU "\n", &in)!=0)
     {
       if (!licznik)
         tablica = (TYP *)malloc((licznik+1)*sizeof(TYP));
       else
         tablica = (TYP *)realloc(tablica,(licznik+1)*sizeof(TYP));
       if (tablica == NULL)
       {
         fprintf(stderr, "Brak pamięci! Program nie może kontynuować działania!\n");
         exit(1);
       }
       tablica[licznik++] = in;
     }
     else
     {
       fscanf(stdin, "%s\n", &smiec);
       fprintf(stderr,"\"%s\" nie jest liczbÄ…! Pozycja zostanie zignorowana!\n", &smiec);
     }
   merge_sort(0, licznik-1);
   for(i = 0; i < licznik; ++i)
   printf("%" OZNACZENIE_TYPU "\n", tablica[i]);
   return 0;
 }

[edytuj] Wersja nierekurencyjna

Podstawową wersję algorytmu sortowania przez scalanie można uprościć. Pomysł polega na odwróceniu procesu scalania serii. Ciąg danych możemy wstępnie podzielić na n serii długości 1, scalić je tak, by otrzymać serii długości 2, scalić je otrzymując , serii długości 4... Złożoność obliczeniowa jest taka sama jak w przypadku klasycznego mergesort, w tym przypadku jednak nie korzystamy z rekursji, a więc zaoszczędzamy czas i pamięć potrzebną na jej obsłużenie.

typedef unsigned int TYP;
 
void MergeSort(TYP* A,unsigned n) // n==Length(A)
{
   unsigned d=1, // dlugosc aktualnej serii
            i,j;   
   while(d<n)
   {
       i=0;j=i+d;
       while(j<n)
       {
          Merge(A[i..i+d],A[j,min(n,j+d)]) //wynik w A[i..2d]
          i+=2d;
          j+=2d;
       }
       d<<=1; //czyli d=d*2;
   }
}