: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > sortowanie >

S O R T O W A N I E   P R Z E Z    S C A L E N I E

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Scalanie ciągów (łączenie) jest operacją połączenia dwóch uporządkowanych rosnąco (malejąco) ciągów elementów w jeden ciąg wynikowy, również uporządkowany rosnąco (malejąco).
Jeśli oba ciągi zapisane są w dwóch osobnych tablicach, zaś ciąg wynikowy ma zostać umieszczony w jeszcze innej trzeciej tablicy sprawa jest w miarę prosta. Znacznie gorzej to wygląda, gdy oba ciągi zapisane są w jednej tablicy, w której to właśnie powinien się znaleźć ciąg wynikowy, a takie mniej więcej warunki stawia algorytm sortowania przez scalanie. Zadanie nie jest niemożliwe, ale kłopotliwe, przynajmiej w zapisie, więc dla uposzczenia sprawy poniższy przykład korzysta z tablicy pomocniczej, do której najpierw przenosi oba ciągi, a następnie z której wykonuje scalanie zapisujac ciąg wynikowy w tablicy źródłowej.

DANE:
a - tablica zawierająca dwa posortowane rosnąco ciągi liczb:
pierwszy od miejsca "start" do miejsca "(start+stop) div 2" (środek),
drugi od miejsca "((start+stop) div 2)+1" do miejsca "stop",
start, stop - indeksy wyznaczające obszar roboczy tablicy
WYNIK:
tablica "a" zawierająca jeden rosnący ciąg liczb utworzony z liczb
dwóch zapisanych w tablicy ciągów rosnących
  1. Przenieś liczby obu ciągów do tablicy pomocniczej,

  2. Dopóki oba ciągi w tablicy pomocniczej są niepuste wykonuj następujace czynności:

    • Z pierwszych wyrazów obu ciągów wybierz mniejszy i zapisz go w tablicy a

  3. Teraz skończył się jeden z ciągów, pozostałe wyrazy w ciągu drugim dopisz do tablicy a

Type
  Tablica = Array[1..1000] Of Integer;

Procedure Scalanie(Var a : Tablica; start, stop : Integer);
Var
  i, i1, i2, sr : Integer;
  tmp           : Tablica;
Begin
  For i:=start To stop Do tmp[i]:=a[i];
  sr:=(start+stop) Div 2;
  i:=start;
  i1:=start;
  i2:=sr+1;
  While (i1<=sr) And (i2<=stop) Do
    Begin
      If tmp[i1]<tmp[i2] Then
        Begin
          a[i]:=tmp[i1];
          i1:=i1+1;
        End
      Else
        Begin
          a[i]:=tmp[i2];
          i2:=i2+1;
        End;
      i:=i+1;
    End;
  If i1>sr Then
    While i2<=stop Do
      Begin
        a[i]:=tmp[i2];
        i2:=i2+1;
        i:=i+1;
      End
  Else
    While i1<=sr Do
      Begin
        a[i]:=tmp[i1];
        i1:=i1+1;
        i:=i+1;
      End;
End;

Sam algorytm sortowania przez scalanie jest przykładem algorytmu rekurencyjnego. Jeśli ciąg zawiera tylko jeden element, to jest już posortowany, jeśli elementy są co najmniej dwa, to dzielimy taki ciąg na połowy, sortujemy przez scalanie lewą i prawą część, a następnie wykonujemy scalenie tych ciągów. 

DANE:
a           - tablica liczb 
start, stop - indeksy wyznaczające obszar roboczy tablicy
WYNIK:
posortowany rosnąco fragment tablicy od miejsca "start" do miejsca 
"stop"
  1. Jeżeli tablica zawiera co najmniej dwie liczby, to:

    • posortuj lewą część tablicy od miejsca start, do miejsca (start+stop) Div 2

    • posortuj prawą część tablicy od miejsca ((start+stop) Div 2)+1 do miejsca stop

    • połącz oba posortowane ciągi w ciąg wynikowy wykonując ich scalanie

Procedure Sort(Var a : Tablica; start, stop : Integer);
Begin
  If start<stop Then
    Begin
      Sort(a, start, (start+stop) Div 2);
      Sort(a, ((start+stop) Div 2)+1, stop);
      Scalanie(a, start, stop);
    End;
End;