czwartek, 13 sierpień 2020
 
Strona główna Algorytmy Sortowanie tablic

Sortowanie tablic

  1. Uwagi wstępne
  2. Sortowanie bąbelkowe (Bubble-sort)
  3. Proste wstawianie (Insert-sort)
  4. Prosty wybor (Selection-sort)
  5. Metoda Shella (Shell-sort)
  6. Metoda stogowa (Heap-sort)
  7. Metoda szybka (Quick-sort)
  8. Metoda łączenia (Merge-sort)

  1. 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;
    

  2. 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
  3. 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
  4. 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
  5. 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
  6. 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:

    1. początkowy rozmiar stogu wynosi n
    2. przekształć nieuporządkowaną tablicę w stóg
    3. zamień wierzchołek stogu z jego ostatnim potomkiem
    4. zmniejsz rozmiar stogu o 1
    5. przywróć własność stogu (przesianie)
    6. 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
  7. 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
  8. 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:

    1. jeżeli początek = koniec to STOP
    2. dzielimy n-elementowy ciąg na dwa podciągi po n/2 elementów każdy
    3. sortujemy tą samą metodą obydwa podciągi
    4. łą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
© mgr inż. Piotr Kotarski, Kalety