Strona Piotr Kotarski

Sortowanie tablic

Uwagi wstępne
Sortowanie bąbelkowe (Bubble-sort)
Proste wstawianie (Insert-sort)
Prosty wybor (Selection-sort)
Metoda Shella (Shell-sort)
Metoda stogowa (Heap-sort)
Metoda szybka (Quick-sort)
Metoda łączenia (Merge-sort)

Uwagi wstępne
program demonstracyjny sort_demo.zip (219kB)

Sortowanie polega na ustawieniu elementów zbioru w kolejności rosnącej lub malejącej według pewnego kryterium (np. wartość liczbowa czy kolejność alfabetyczna tekstów). Z punktu widzenia techniki komputerowej rozróżnia się dwie grupy metod:
1. sortowanie tablic, czyli wszystkie dane są w każdej chwili dostępne (in situ)
2. sortowanie plików, czyli dane są dostępne sekwencyjnie
Sortowanie tablic jest łatwiejsze i w literaturze można spotkac opis wielu metod różniących się szybkością i złożonością algorytmu. Sortowanie plików jest sprawą bardziej złożoną i z reguły wymaga tworzenia dodatkowych plików pomocniczych. Poniżej opisane są najważniejsze metody sortowania.

Założenie: w procedurach dotyczących sortowania tablic zakładam następujące deklaracje:
Deklaracje
```
const  n= RozmiarTablicy;
type   typ= OpisTypuElementuTablicy;
var    x: array[1..n] of typ;
```

Sortowanie metodą prostej zamiany (sortowanie bąbelkowe)

Polega na przeglądaniu tablicy i porównywaniu par sąsiednich elementów. Jeżeli ich porządek nie jest właściwy, to są zamieniane miejscami. Po jednym przejrzeniu tablicy ostatni jej element jest już na właściwym miejscu, dlatego można go pominąć w następnym przebiegu.

BubbleSort

procedure BubbleSort;
var     i,j:    integer;
        pom:    typ;
begin
    for i:=n-1 downto 1 do
        for j:=1 to i do
            if x[j]>x[j+1] then
            begin
                pom:=x[j];
                x[j]:=x[j+1];
                x[j+1]:=pom;
            end;
end;

do góry

Sortowanie metodą prostego wstawiania

Metoda polega na przesiewaniu kolejnych elementów w kierunku początku tablicy aż do znalezienia właściwego miejsca. W czasie sortowania początkowa część tablicy jest już uporządkowana. Na początku zakłada się, że pierwszy element jest na właściwym miejscu. Następny element porównuje się z poprzednim i w razie potrzeby przesuwa się go w tył aż się znajdzie na swoim miejscu.
Metoda jest znana wszystkim karciarzom, gdyż właśnie w ten sposób zwykle porządkują karty w ręku.

InsertSort

procedure InsertSort;
var     i,j:   integer;
        bufor: typ;
begin
    for i:=2 to n do
    begin
        bufor:=x[i];
        j:=i-1;
        while x[j]>bufor do
        begin
            x[j+1]:=x[j];
            dec(j);
            if j=0 then break;
        end;
        x[j+1]:=bufor;
    end;
end;

do góry

Sortowanie metodą prostego wyboru

W czasie sortowania początkowa część tablicy jest już uporządkowana. Na początku część uporządkowana jest pusta. Metoda polega na wyszukiwaniu w części nieuporząkowanej elementu najmniejszego, a następnie zamianie go z pierwszym elementem części nieuporządkowanej (staje się ostatnim elementem części uporządkowanej).
Metoda ta wymaga bardzo dużej liczby porównań elementów.

Selection-Sort

procedure SelectionSort;
var     i,j,k:  integer;
        pom:    typ;
begin
    for i:=1 to n-1 do
    begin
        k:=i;
        for j:=i+1 to n do
            if x[j]<x[k] then k:=j;
        if k>i then
        begin
            pom:=x[k];
            x[k]:=x[i];
            x[i]:=pom
        end;
    end;
end;

do góry

Sortowanie metodą Shella

Jest to zmodyfikowana metoda wstawiania. Można zauważyć, że przy wstawianiu elementu o małej wartości musi on "ominąć" dużą liczbę większych elementów. Wynika to stąd, że porównujemy i przestawiamy sąsiednie elementy. W metodzie Shella początkowo porównuje się elementy oddalone np. o połowę rozmiaru tablicy. W wyniku pierwszego przebiegu tablica jest już posortowana "co n/2". W drugim przebiegu sortujemy co n/4 rozmiaru, potem n/8, itd. Ostatni przebieg jest już zwykłym wstawianiem "co 1", ale z powodu znacznego uporządkowania tablicy element jest przesiewany na niewielką odległość.

Tak opisany sposób realizuje ciąg odległości (czytany od końca):

1 2 4 8 16 ...2*k

Shell-Sort (1 2 4 8 ...)

procedure shell124;
var     i,j,k:  integer;
        bufor:  typ;
begin
    k:=n div 2;
    repeat
        for i:=k+1 to n do
        begin
            bufor:=x[i];
            j:=i-k;
            while x[j]>bufor do
            begin
                x[j+k]:=x[j];
                j:=j-k;
                if j<1 then break
            end;
            x[j+k]:=bufor
        end;
        k:=k div 2;
    until k=0;
end;

W wyniku analizy metody okazało się, że lepsze wyniki dają inne ciągi odległości. Najlepiej, gdy wyrazy ciągu nie są swoimi dzielnikami, np:

1  3  7  15 ... 2*k+1
1  2  5  14 ... 3*k-1
1  4 13  40 ... 3*k+1

Shell-Sort (1 4 13 40 ...)

procedure shell1413;
var     i,j,k:  integer;
        pom:    typ;
begin
    i:=1;
    repeat
        k:=i;
        i:=3*k+1;
    until i>n;
    repeat
        for i:=k+1 to n do
        begin
            pom:=x[i];
            j:=i-k;
            while x[j]>pom do
            begin
                x[j+k]:=x[j];
                j:=j-k;
                if j<1 then break
            end;
            x[j+k]:=pom;
        end;
        k:=(k-1) div 3;
    until k=0;
end;

do góry

Sortowanie metodą stogową

Metoda wykorzystuje strukturę zwaną stogiem (stosowane są również nazwy sterta i kopiec). Jest to drzewo binarne o kształcie jak na rysunku:

Kształt stogu

Cechą wyróżniającą stóg jest jego uporządkowanie:
wartość każdego węzła jest większa od wartości jego potomków.

Przykład stogu

Stóg można bardzo łatwo reprezentować w zwykłej tablicy czytając je kolejnymi rzędami. Odpowiada to następującym regułom:

tab[1]     - wierzchołek stogu
tab[2*n]   - lewy potomek węzła n
tab[2*n+1] - prawy potomek węzła n

Reprezentacja stogu w tablicy

Istotną procedurą pomocniczą jest przesianie. Jej celem jest przywrócenie właściwości stogu po zmianie wartości jego wierzchołka. Jest ona wykorzystywana w etapie tworzenia stogu oraz w etapie sortowania.

Algorytm sortowania:

początkowy rozmiar stogu wynosi n
przekształć nieuporządkowaną tablicę w stóg
zamień wierzchołek stogu z jego ostatnim potomkiem
zmniejsz rozmiar stogu o 1
przywróć własność stogu (przesianie)
dopóki n>1 powtórz pkt. 3

Heap-Sort

procedure heapsort;
var     lewy,prawy:    integer;
        pom:    typ;
procedure przesianie;
var     i,j:    integer;
        pom:    typ;
begin
    i:=lewy;
    j:=2*i;
    pom:=x[i];
    while j<=prawy do
    begin
        if (j<prawy) and (x[j]<x[j+1]) then
            Inc(j);
        if pom>x[j] then
            break;
        x[i]:=x[j];
        i:=j;
        j:=2*i;
    end;
    x[i]:=pom
end;

begin   lewy:=(n div 2)+1;
        prawy:=n;
        while lewy>1 do
         begin   Dec(lewy);
                 przesianie
         end;
        while prawy>1 do
         begin   pom:=x[lewy];
                 x[lewy]:=x[prawy];
                 x[prawy]:=pom;
                 Dec(prawy);
                 przesianie
         end;
end;

do góry

Sortowanie metodą szybką

Jest to metoda, która w typowych przypadkach działa bardzo szybko (stąd nazwa). Odkrył ją w latach 60-tych XXw profesor Tony Hoare. Procedura wywoływana jest z dwoma parametrami określającymi indeksy pierwszego i ostatniego elementu.

wywołanie procedury quicksort

       quicksort(1,n);

Najpierw wybierany jest tzw. element osiowy, którym może być dowolny z elementów tablicy (np pierwszy lub środkowy). Następnie tablica jest dzielona na dwie części. W lewej są elementy mniejsze od osiowego, w prawej większe. Poniższe procedury prezentują dwa sposoby podziału. Różnią się one złożonością obliczeniową. Pierwszy charakteryzuje się mniejszą liczbą operacji podstawienia, drugi mniejszą liczbą operacji porównania.
Następnie rekurencyjnie sortuje się obydwie części, o ile ich rozmiary są większe od 1.
I JUŻ!

Quick-sort - sposób 1

procedure quicksort(lewy,prawy:integer);
var     i,j:    integer;
        w,pom:  typ;
begin   i:=lewy;
        j:=prawy;
        w:=x[(lewy+prawy) div 2];
        repeat  while w>x[i] do Inc(i);
                while x[j]>w do Dec(j);
                if i<=j then
                begin   pom:=x[i];
                        x[i]:=x[j];
                        x[j]:=pom;
                        Inc(i);
                        Dec(j)
                end;
        until i>j;
        if lewy<j then quicksort(lewy,j);
        if i<prawy then quicksort(i,prawy);
end;

Quick-sort - sposób 2

procedure quicksort2(lewy,prawy:integer);
var     i,j     :integer;
        pom     :typ;
begin   if lewy<prawy then
        begin   j:=lewy;
                for i:=lewy+1 to prawy do
                if x[lewy]>x[i] then
                begin   Inc(j);
                        pom:=x[i];
                        x[i]:=x[j];
                        x[j]:=pom;
                end;
                pom:=x[lewy];
                x[lewy]:=x[j];
                x[j]:=pom;
                quicksort2(lewy,j-1);
                quicksort2(j+1,prawy);
        end;
end;

do góry

Sortowanie metodą łączenia (scalanie)

Metoda ta jest adaptacją dla tablic metody stosowanej do sortowania plików. Jest metodą rekurencyjną z gatunku "dziel i zwyciężaj".
Procedura sortująca otrzymuje dwa parametry oznaczające początek i koniec sortowanego ciągu (fragmentu tablicy):

Wywołanie procedury Merge-sort

   mergesort(1,n);

Algorytm jest prosty:

jeżeli początek = koniec to STOP
dzielimy n-elementowy ciąg na dwa podciągi po n/2 elementów każdy
sortujemy tą samą metodą obydwa podciągi
łączymy podciągi w jeden posortowany ciąg

Merge-sort

procedure mergesort(lewy,prawy:Integer);
var     i,d,m,w1,w2: Integer;
        pom:    array[0..n-1] of typ;
begin   if lewy<>prawy then
        begin   d:=(prawy-lewy) div 2;
                m:=lewy+d;
                mergesort(lewy,m);
                mergesort(m+1,prawy);
                w1:=lewy;
                w2:=m+1;
                for i:=0 to prawy-lewy do
                if (w1>m) or (w2<=prawy)
                   and (x[w1]>x[w2])
                then begin   pom[i]:=x[w2];
                             w2:=w2+1
                     end
                else begin   pom[i]:=x[w1];
                             w1:=w1+1
                     end;
                for i:=0 to prawy-lewy do
                        x[lewy+i]:=pom[i];
        end
end;

do góry