Sortowanie przez scalanie

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

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

Algorytm ten jest dobrym przykładem algorytmów typu Dziel i rządź (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.

Tutaj można wyróżnić trzy podstawowe kroki:

Podziel zestaw danych na dwie, równe części;
Zastosuj sortowanie przez scalanie dla każdej z nich odzielnie, chyba że pozostał już tylko jeden element;
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]:

Uwórz wskaźniki na początki ciągów A i B -> i=0, j=0
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
Powtarzaj krok 2 aż wszystkie wyrazy A i B trafią do C

A więc scalenie dwóch wymaga O(n+m) operacji porównań elementów i wstawienia ich do tablicy wynikowej.

Spis treści

1 Złożoność czasowa algorytmu sortowania przez scalanie
2 Dowód poprawności algorytmu sortowania przez scalanie
3 Przykład kodu źródłowego
4 Wersja nierekurencyjna

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

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)

Poniższy obrazek 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)$
$T(n) = 2T(\frac{n}{2}) + O(n)$

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

Mamy:

$T(n) = 2T(\frac{n}{2}) + n = 2(2T(\frac{n}{4}) + \frac{n}{2}) + n = 2(2(2(T(\frac{n}{4}) + \frac{n}{4}) + \frac{n}{2}) + n = 2(2(...2( (T(\frac{n}{2^k}=1) +1)+2)+4)+...)+\frac{n}{2})+n$

gdzie $n = 2 k$

Po rozwinięciu nawiasów otrzymamy:

$T (n) = 2 n l o g n$

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 2 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 1go, posortowanego ciągu długości n.

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

Język: SML

fun merge (nil,nil) = nil
|   merge (l,nil) = l
|   merge (nil,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 nil = nil
|   odd (x::xs) = even xs
and even nil = nil
|   even (x::xs) = x::odd xs

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

(* np. sortuj int list*)
mergesort [108, 15, 15, 3, 14, 15, 108];

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ć $\frac{n}{2}$ serii długości 2, scalić je otrzymując $\frac{n}{4}$ , serii długości 4... Złożość obliczeniowa jest taka sama jak w przypadku klasycznego mergesort, w tym przypadku jednak nie korzystamy z rekursjii, 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*=2;
   }
}

Źródło: "http://pl.wikipedia.org../../../s/o/r/Sortowanie_przez_scalanie.html"

Kategoria: Sortowanie