Matura - programowanie w C++

Sortowanie danych (ang. data sort) jest jednym z podstawowych problemów programowania komputerów, z którym prędzej czy później spotka się każdy programista. Poniżej przedstawiono kilka zastosowań sortowania danych:

Zainteresowanych głębiej problemami sortowania odsyłam do artykułu o algorytmach sortujących.

Zaczniemy od jednego z najprostszych algorytmów sortujących, zwanego Sortowaniem Bąbelkowym (ang. buble sort). Zasada działania jest następująca:

 { 8 2 6 3 1 } → { 1 2 3 6 8 }

Zwróć uwagę na kilka rzeczy. W każdym obiegu elementy kolejno największe są przesuwane w kierunku końca zbioru. Element najmniejszy jest natomiast przesuwany o jedną pozycję w kierunku początku zbioru. Zatem jeśli element najmniejszy był na końcu zbioru na pozycji n - 1, to aby trafił na pozycję 0, potrzeba n - 1 przesunięć, dlatego wymagane jest n - 1 obiegów.

W algorytmie będą dwie pętle: pętla zewnętrzna zliczająca obiegi oraz zagnieżdżona pętla wewnętrzna przeglądająca pary kolejnych elementów. Jeśli zbiór ma n elementów, to tworzą one n - 1 kolejnych par:

{ 1 2 3 4 5 } → { 1 2 }   { 2 3 }   { 3 4 }   { 4 5 }

Dlatego pętla wewnętrzna też będzie wykonywać n - 1 obiegów przy każdym obiegu pętli zewnętrznej. Otrzymamy zatem obiegów:

(n - 1) · (n - 1) = n2 - 2n + 1

Przy dużych n możemy pominąć -2n i 1, otrzymamy w przybliżeniu n² obiegów, zatem algorytm będzie miał kwadratową klasę czasowej złożoności obliczeniowej O(n²).

Algorytm Sortowania Bąbelkowego – wersja 1

K01: Dla i = 0,1,...,n-2:   ; pętla zewnętrzna
     wykonuj kroki K02...K03
K02:   Dla j = 0,1,...,n-2: ; pętla zagnieżdżona
       wykonuj krok K03
K03:     Jeśli T[j] > T[j + 1], to ; jeśli w złej kolejności,
           T[j] ↔ T[j + 1]  ; zamień miejscami
K04: Zakończ

Poniższy program tworzy tablicę 100 elementową i wypełnia ją liczbami pseudolosowymi od 0 do 999. Wyświetla tablicę nieposortowaną, następnie sortuje ją algorytmem bąbelkowym i wyświetla wynik.

// Sortowanie Bąbelkowe
//---------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

// Funkcja sortująca
//------------------
void BubleSort(int n, int T[])
{
    int i,j;
    for(i = 0; i < n - 1; i++)
        for(j = 0; j < n - 1; j++)
            if(T[j] > T[j + 1])
                swap(T[j],T[j + 1]);
}

// Funkcja wyświetla tablicę
//--------------------------
void piszT(int n, int T[])
{
    for(int i = 0; i < n; i++)
        cout << setw(4) << T[i];
    cout << endl;
}

int main()
{
    // inicjujemy LCG
    srand(time(NULL));

    // tworzymy tablicę
    const int N = 100;
    int T[N],i;
    for(i = 0; i < N; i++)
        T[i] = rand() % 1000;

    // wyświetlamy tablicę nieposortowaną
    cout << "Tablica przed sortowaniem:" << endl << endl;
    piszT(N,T);

    // sortujemy
    BubleSort(N,T);

    // wyświetlamy tablicę po sortowaniu
    cout << "Tablica po sortowaniu:" << endl << endl;
    piszT(N,T);

    return 0;
}

Tablica przed sortowaniem:

 406 365 164 713  75 415 852 563 951 620 544 853  54 322 539 309 732 588 851 880
 397 398 558 556 934 769 565 107 811 480 779  30 579 178 791 992 688 593 207 461
 172 473 112 659 113 245 804 504 679 335 372 620 267 510 318  80 829  13 872 495
 403 818 606 652 749 364 352 692 673 993 279 365 224  54 985 552  56   8 131 675
  59 395 639 289 616 377 831 982   1 901 368 190  85 401 306 917 518 317 399 581

Tablica po sortowaniu:

   1   8  13  30  54  54  56  59  75  80  85 107 112 113 131 164 172 178 190 207
 224 245 267 279 289 306 309 317 318 322 335 352 364 365 365 368 372 377 395 397
 398 399 401 403 406 415 461 473 480 495 504 510 518 539 544 552 556 558 563 565
 579 581 588 593 606 616 620 620 639 652 659 673 675 679 688 692 713 732 749 769
 779 791 804 811 818 829 831 851 852 853 872 880 901 917 934 951 982 985 992 993 

Przedstawiony algorytm jest bardzo prymitywny i jego jedyną chyba zaletą jest to, iż działa. Postarajmy się go ulepszyć.

Zauważ, iż w pierwszym obiegu pętli wewnętrznej liczba największa w zbiorze zostaje zawsze przesunięta na koniec zbioru, a zatem trafia na swoje miejsce docelowe. W drugim obiegu nie ma sensu jej już porównywać z liczbą poprzednią. Zatem możemy założyć, iż po pierwszym obiegu, element końcowy jest posortowany. Dlatego w drugim obiegu można zbiór zmniejszyć o ten element i sortować n - 1 liczb. W drugim obiegu znów liczba największa w tym zredukowanym zbiorze trafi na koniec i będziemy mieli już dwa największe elementy posortowane. Procedurę tę możemy kontynuować i po każdym obiegu pętli zewnętrznej zmniejszać o 1 liczbę elementów do posortowania, "wyrzucając" ostatni element. W ten sposób algorytm będzie działał szybciej, gdyż będzie systematycznie malała liczba elementów do posortowania.

Zobaczmy to na przykładzie sortowania zbioru { 8 2 6 3 1 }:

 { 8 2 6 3 1 } → { 1 2 3 6 8 }

Zauważ rzecz drugą: Jeśli zbiór jest posortowany, to nie wystąpi żadna zamiana miejsc elementów. Zatem musimy sprawdzać po wykonaniu obiegu zewnętrznego, czy wystąpiła zamiana miejsc elementów. Jeśli nie, to kończymy sortowanie. Jak to zrealizować w algorytmie? Bardzo prosto. Tworzymy zmienną logiczną, np. o nazwie ok. Na początku każdego obiegu pętli zewnętrznej nadajemy jej wartość true. W pętli wewnętrznej przy zamianie elementów zmieniamy wartość tej zmiennej na false. Po każdym obiegu zewnętrznym sprawdzamy, czy ok ma wartość true. Jeśli tak, to nie było przestawienia elementów, czyli zbiór jest posortowany i możemy zakończyć algorytm.

Algorytm Sortowania Bąbelkowego – wersja 2

K01: Dla i = 0,1,...,n-2:     ; pętla zewnętrzna, n-1 obiegów
     wykonuj kroki K02...K07
K02:   ok ← true              ; sprawdza posortowanie zbioru
K03:   Dla j = 0,1,...,n-i-2: ; pętla zagnieżdżona, malejąca ilość obiegów
       wykonuj kroki K04...K06
K04:     Jeśli T[j] ≤ T[j + 1],
         to następny obieg pętli K02
K05:     T[j] ↔ T[j + 1]      ; zamieniamy miejscami elementy
K06:     ok ← false           ; zapamiętujemy zamianę
K07:   Jeśli ok = true,       ; brak zamiany, zbiór posortowany
       to zakończ
K08: Zakończ

W poprzednim programie wymień funkcję bublesort( ) na poniższą:

...
// Funkcja sortująca
//------------------
void BubleSort(int n, int T[])
{
    int i,j;
    bool ok;
    for(i = 0; i < n-1; i++)
    {
        ok = true;
        for(j = 0; j < n-i-1; j++)
            if(T[j] > T[j + 1])
            {
                swap(T[j],T[j + 1]);
                ok = false;
            }
        if(ok) break;
    }
}
...

Sortowanie Bąbelkowe uważane jest za zły algorytm sortujący i w praktyce można go stosować do niedużych zbiorów (do około 5000 elementów). Klasa czasowej złożoności obliczeniowej Sortowania Bąbelkowego jest równa O(n²). Przy sortowaniu większych zbiorów należy wybrać lepszy algorytm.

Przy sortowaniu algorytm nie wymaga dodatkowego miejsca w pamięci komputera, tylko obszar dla n sortowanych elementów, zatem klasa pamięciowej złożoności obliczeniowej jest równa O(1).

Algorytm wykonuje sortowanie bezpośrednio na sortowanym zbiorze, taką własność nazywamy sortowaniem w miejscu (ang. in-place sorting).

Jeśli zbiór zawiera elementy równe, to po sortowaniu elementy te nie zmieniają kolejności względem siebie. Taka własność nosi nazwę stabilności (ang. stability). Przy sortowaniu zwykłych liczb nie ma to znaczenia. Jeśli jednak sortowane elementy są jakimiś obiektami, to sortowanie odbywa się wg klucza (np. numeru obiektu) i czasem kolejność elementów o równych kluczach jest istotna.

Podsumowanie:

Zadanie:

Zmodyfikuj algorytm 2 tak, aby sortował zbiór malejąco.

Do zapamiętania:

• Algorytm Sortowania Bąbelkowego 1 i 2.
• Własności algorytmu Sortowania Bąbelkowego.

Załóżmy, iż chcemy posortować zbiór rosnąco. Szukamy w zbiorze elementu najmniejszego. Gdy element ten znajdziemy, wymieniamy go z pierwszym elementem. Element najmniejszy znajdzie się na swojej docelowej pozycji. Redukujemy zbiór tak, aby pierwszy element do niego już nie należał. W tak zredukowanym zbiorze ponownie wyszukujemy kolejny element najmniejszy i wymieniamy go z elementem na początku zbioru. Procedurę kontynuujemy, aż zbiór zredukuje się do 1 elementu. Elementy usunięte będą tworzyły zbiór uporządkowany.

Zobaczmy na prostym przykładzie działanie tego algorytmu. Posortujemy zbór: { 5 4 6 3 1 2 }

Algorytm Sortowania przez Wybór

K01: Dla i = 0,1,...,n-2: ; pozycje początku zbioru
     wykonuj kroki K02...K05
K02:   p ← i              ; szukamy elementu najmniejszego
K03:   Dla j = i + 1, i + 2,... , n - 1:
       wykonuj krok K04
K04:     Jeśli T[j] < T[p],
         to p ← j
K05:   T[i] ↔ T[p]        ; wymieniamy najmniejszy z początkowym
K06: Zakończ

Poniższy program jest programem z poprzedniego rozdziału, w którym sortowanie jest wykonywane nowym algorytmem.

// Sortowanie przez Wybór
//-----------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

// Funkcja sortująca
//------------------
void SelectionSort(int n, int T[])
{
    int i,j,p;
    for(i = 0; i < n - 1; i++)
    {
        p = i;
        for(j = i+1; j < n; j++)
            if(T[j] < T[p]) p = j;
        swap(T[i],T[p]);
    }
}

// Funkcja wyświetla tablicę
//--------------------------
void piszT(int n, int T[])
{
    for(int i = 0; i < n; i++)
        cout << setw(4) << T[i];
    cout << endl;
}

int main()
{
    // inicjujemy LCG
    srand(time(NULL));

    // tworzymy tablicę
    const int N = 100;
    int T[N],i;
    for(i = 0; i < N; i++)
        T[i] = rand() % 1000;

    // wyświetlamy tablicę nieposortowaną
    cout << "Tablica przed sortowaniem:" << endl << endl;
    piszT(N,T);

    // sortujemy
    SelectionSort(N,T);

    // wyświetlamy tablicę po sortowaniu
    cout << "Tablica po sortowaniu:" << endl << endl;
    piszT(N,T);

    return 0;
}

Sortowanie przez Wybór ogólnie jest szybsze od przedstawionego w poprzednim rozdziale Sortowania Bąbelkowego. W algorytmie mamy dwie pętle: zewnętrzną i zagnieżdżoną. Klasa czasowej złożoności obliczeniowej jest kwadratowa O(n²). Ponieważ algorytm wymienia kolejne elementy z początku zbioru ze znalezionymi elementami najmniejszymi, elementy równe nie zachowują pozycji względem siebie, zatem algorytm nie jest stabilny. Elementy są sortowane w tym samym zbiorze, zatem sortowanie odbywa się w miejscu i algorytm nie potrzebuje dodatkowej pamięci, dlatego jego klasa pamięciowej złożoności obliczeniowej jest równa O(1).

Podsumowanie:

Zadanie:

Zmodyfikuj algorytm tak, aby sortował zbiór malejąco.

Do zapamiętania:

• Algorytm Sortowania przez Wybór.
• Własności algorytmu Sortowania przez Wybór.

Algorytm Sortowania przez Wstawianie można porównać do sposobu układania w ręce kart pobieranych z talii. Najpierw bierzemy pierwszą kartę. Następnie pobieramy kolejne, aż do wyczerpania talii. Każdą pobraną kartę porównujemy z kartami, które już trzymamy w ręce i szukamy dla niej miejsca przed pierwszą kartą starszą (młodszą w przypadku porządku malejącego). Gdy znajdziemy takie miejsce, rozsuwamy karty i nową wstawiamy na przygotowane w ten sposób miejsce (stąd pochodzi nazwa algorytmu - Sortowanie przez Wstawianie, ang. Insertion Sort). Jeśli nasza karta jest najstarsza (najmłodsza), to umieszczamy ją na samym końcu. Tak porządkujemy karty. A jak przenieść tę ideę do świata komputerów i zbiorów liczbowych?

Algorytm Sortowania przez Wstawianie będzie składał się z dwóch pętli. Pętla główna (zewnętrzna) symuluje pobieranie kart, czyli w tym wypadku elementów zbioru. Odpowiednikiem kart na ręce jest tzw. lista uporządkowana (ang. sorted list), którą sukcesywnie będziemy tworzyli na końcu zbioru (istnieje też odmiana algorytmu umieszczająca listę uporządkowaną na początku zbioru). Pętla sortująca (wewnętrzna) szuka dla pobranego elementu miejsca na liście uporządkowanej. Jeśli takie miejsce zostanie znalezione, to elementy listy są odpowiednio rozsuwane, aby tworzyć miejsce na nowy element i element wybrany przez pętlę główną trafia tam. W ten sposób lista uporządkowana rozrasta się. Jeśli na liście uporządkowanej nie ma elementu większego od wybranego, to element ten trafia na koniec listy. Sortowanie zakończymy, gdy pętla główna wybierze wszystkie elementy zbioru.

Wstawianie elementu na listę uporządkowaną

Najważniejszą operacją w opisywanym algorytmie sortowania jest wstawianie wybranego elementu na listę uporządkowaną. Zasady są następujące:

1. Na początku sortowania lista uporządkowana zawiera tylko jeden, ostatni element zbioru. Jednoelementowa lista jest zawsze uporządkowana.
2. Ze zbioru zawsze wybieramy element leżący tuż przed listą uporządkowaną. Element ten zapamiętujemy w zewnętrznej zmiennej. Miejsce, które zajmował, możemy potraktować jak puste.
3. Wybrany element porównujemy z kolejnymi elementami listy uporządkowanej.
4. Jeśli natrafimy na koniec listy, element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.
5. Jeśli element listy jest większy od wybranego, to element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.
6. Jeśli element listy nie jest większy od wybranego, to element listy przesuwamy na puste miejsce. Dzięki tej operacji puste miejsce wędruje na liście przed kolejny element. Kontynuujemy porównywanie, aż wystąpi sytuacja z punktu 4 lub 5.

Przykład:

 7  1  3  5  9 

 7 
    1  3  5  9 

    7 
 <<<1  3  5  9 

    7 
 1     3  5  9 

       7 
 1  <<<3  5  9 

       7 
 1  3     5  9 

          7 
 1  3  <<<5  9 

          7 
 1  3  5     9 

          <<<7 
 1  3  5     9 

 1  3  5  7  9 

Algorytm Sortowania przez Wstawianie

K01: Dla j = n-2,n-3,...,0: ; indeksy sortowanych elementów
     wykonuj kroki K02...K09
K02:   x ← T[j]             ; zapamiętujemy sortowany element
K03:   i ← j + 1            ; przeglądamy listę od następnej pozycji
K04:   Jeśli i = n,         ; koniec listy?
       to idź do kroku K09
K05:   Jeśli x ≤ T[i],      ; element listy większy lub równy?
       to idź do kroku K09
K06:   T[i-1] ← T[i]        ; przesuwamy element listy w dół
K07:   i ← i + 1            ; następny element listy do sprawdzenia
K08:   Idź do kroku K04     ; kolejny obieg pętli
K09:   T[i-1] ← x           ; sortowany element wstawiamy na listę
K10: Zakończ

Poniższy program jest programem z poprzedniego rozdziału, w którym sortowanie jest wykonywane nowym algorytmem.

// Sortowanie przez Wstawianie
//----------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

// Funkcja sortująca
//------------------
void InsertionSort(int n, int T[])
{
    int i,j,x;
    for(j = n - 2; j >= 0; j--)
    {
        x = T[j];                //  Sortowany element
        for(i = j + 1; i < n; i++)
        {
            if(x <= T[i]) break; // Element listy większy?
            T[i - 1] = T[i];     // Nie, przesuwamy go
        }                        // w dół listy
        T[i - 1] = x;            // Tak, wstawiamy na listę
    }                            // element x
}

// Funkcja wyświetla tablicę
//--------------------------
void piszT(int n, int T[])
{
    for(int i = 0; i < n; i++)
        cout << setw(4) << T[i];
    cout << endl;
}

int main()
{
    // inicjujemy LCG
    srand(time(NULL));

    // tworzymy tablicę
    const int N = 100;
    int T[N],i;
    for(i = 0; i < N; i++)
        T[i] = rand() % 1000;

    // wyświetlamy tablicę nieposortowaną
    cout << "Tablica przed sortowaniem:" << endl << endl;
    piszT(N,T);

    // sortujemy
    InsertionSort(N,T);

    // wyświetlamy tablicę po sortowaniu
    cout << "Tablica po sortowaniu:" << endl << endl;
    piszT(N,T);

    return 0;
}

Podsumowanie:

Do zapamiętania:

• Algorytm Sortowania przez Wstawianie.
• Własności algorytmu Sortowania przez Wstawianie.

Poczynając od tego rozdziału przechodzimy do opisu algorytmów szybkich, tzn. takich, które posiadają klasę czasowej złożoności obliczeniowej równą O(n·log n) lub nawet lepszą.

W informatyce zwykle obowiązuje zasada, iż prosty algorytm posiada dużą złożoność obliczeniową, natomiast algorytm zaawansowany posiada małą złożoność obliczeniową, ponieważ wykorzystuje on pewne własności, dzięki którym szybciej dochodzi do rozwiązania.

Wiele dobrych algorytmów sortujących korzysta z rekurencji, która powstaje wtedy, gdy do rozwiązania problemu algorytm wykorzystuje samego siebie ze zmienionym zestawem danych.

Wynaleziony w 1945 roku przez Johna von Neumanna algorytm Sortowania przez Scalanie (ang. Merge Sort) jest algorytmem rekurencyjnym. Wykorzystuje zasadę dziel i zwyciężaj, która polega na podziale zadania głównego na zadania mniejsze dotąd, aż rozwiązanie stanie się oczywiste. Algorytm sortujący dzieli porządkowany zbiór na kolejne połowy dopóki taki podział jest możliwy (tzn. podzbiór zawiera co najmniej dwa elementy). Następnie uzyskane w ten sposób części zbioru rekurencyjnie sortuje tym samym algorytmem. Posortowane części łączy ze sobą za pomocą scalania, tak aby wynikowy zbiór był posortowany.

Scalanie dwóch zbiorów uporządkowanych

Podstawową operacją algorytmu jest scalanie dwóch zbiorów uporządkowanych w jeden zbiór również uporządkowany. Operację scalania realizujemy wykorzystując pomocniczy zbiór, w którym będziemy tymczasowo odkładać scalane elementy dwóch zbiorów. Ogólna zasada jest następująca:

1. Przygotuj pusty zbiór tymczasowy

2. Dopóki żaden ze scalanych zbiorów nie jest pusty, porównuj ze sobą pierwsze elementy każdego z nich i w zbiorze tymczasowym umieszczaj mniejszy z elementów usuwając go jednocześnie ze scalanego zbioru.

3. W zbiorze tymczasowym umieść zawartość tego scalanego zbioru, który zawiera jeszcze elementy.

4. Zawartość zbioru tymczasowego przepisz do zbioru wynikowego i zakończ algorytm.

Przykład:

Połączmy za pomocą opisanego algorytmu dwa uporządkowane zbiory: { 1 3 6 7 9 } z { 2 3 4 6 8 } :

[1] 3  6  7  9 
 2  3  4  6  8 

    3  6  7  9 
 2  3  4  6  8 

 1 

    3  6  7  9 
[2] 3  4  6  8 

 1 

   [3] 6  7  9 
    3  4  6  8 

 1 2 

       6  7  9 
   [3] 4  6  8 

 1 2 3 

       6  7  9 
      [4] 6  8 

 1 2 3 3 

      [6] 7  9 
          6  8 

 1 2 3 3 4 

          7  9 
         [6] 8 

 1 2 3 3 4 6 

         [7] 9 
             8 

 1 2 3 3 4 6 6 

             9 
            [8]

 1 2 3 3 4 6 6 7 

            [9]

 1 2 3 3 4 6 6 7 8 

 1 2 3 3 4 6 6 7 8 9 

Przed przystąpieniem do wyjaśniania sposobu łączenia dwóch zbiorów uporządkowanych w jeden zbiór również uporządkowany musimy zastanowić się nad sposobem reprezentacji danych. Przyjmijmy, iż elementy zbioru będą przechowywane w jednej tablicy, którą oznaczymy jako d[ ]. Każdy element w tej tablicy będzie posiadał swój numer, czyli indeks z zakresu od 0 do n-1.

Kolejnym zagadnieniem jest sposób reprezentacji scalanych zbiorów. W przypadku algorytmu Sortowania przez Scalanie zawsze będą to dwie przyległe połówki zbioru, który został przez ten algorytm podzielony. Co więcej, wynik scalenia ma być umieszczony z powrotem w tym samym zbiorze.

Przykład:

Prześledźmy prosty przykład. Mamy posortować zbiór o postaci: { 6 5 4 1 3 7 9 2 }

Ponieważ w opisywanym tutaj algorytmie sortującym scalane podzbiory są przyległymi do siebie częściami innego zbioru, zatem logiczne będzie użycie do ich definicji indeksów wybranych elementów tych podzbiorów:

Przez podzbiór młodszy rozumiemy podzbiór zawierający elementy o indeksach mniejszych niż indeksy elementów w podzbiorze starszym.

Indeks końcowego elementu młodszej połówki zbioru z łatwością wyliczamy - będzie on o 1 mniejszy od indeksu pierwszego elementu starszej połówki.

Przykład:

Specyfikacja algorytmu scalania

Scalaj(d, ip, is, ik)

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków algorytmu scalania

K01: i1 ← ip ; początek partycji młodszej
K02: i2 ← is ; początek partycji starszej
K03: Dla i = ip,ip+1,...,ik: ; scalamy obie partycje
     wykonuj kroki K04...K11
K04:   Jeśli i1 = is,        ; koniec partycji młodszej?
       to idź do kroku K10
K05:   Jeśli i2 = ik+1,      ; koniec partycji starszej?
       to idź do kroku K07
K06:   Jeśli d[i2] < d[i1],  ; element starszy mniejszy od młodszego?
       to idź do kroku K10
K07:   p[i] ← d[i1]          ; element młodszy do p
K08:   i1 ← i1 + 1
K09:   Następny obieg pętli K3
K10:   p[i] ← d[i2]          ; element starszy do p
K11:   i2  ← i2 + 1
K12: Dla i = ip,ip+1,...,ik: ; p do d
     wykonuj d[i] ← p[i]
K13: Zakończ

Operacja scalania dwóch podzbiorów wymaga dodatkowej pamięci o rozmiarze równym sumie rozmiarów scalanych podzbiorów. Dla prostoty na potrzeby naszego algorytmu zarezerwujemy tablicę p o rozmiarze równym rozmiarowi tablicy d. W tablicy p algorytm będzie tworzył zbiór tymczasowy, który po zakończeniu scalania zostanie przepisany do tablicy d w miejsce dwóch scalanych podzbiorów.

Parametrami wejściowymi do algorytmu są indeksy ip, is oraz ik, które jednoznacznie definiują położenie dwóch podzbiorów do scalenia w obrębie tablicy d. Elementy tych podzbiorów będą indeksowane za pomocą zmiennych i1 (młodszy podzbiór od pozycji ip do is - 1) oraz i2 (starszy podzbiór od pozycji is do ik). Na początku algorytmu przypisujemy tym zmiennym indeksy pierwszych elementów w każdym podzbiorze.

Zmienna i będzie zawierała indeksy elementów wstawianych do tablicy p. Dla ułatwienia indeksy te przebiegają wartości od ip do ik, co odpowiada obszarowi tablicy d zajętemu przez dwa scalane podzbiory. Na początku do zmiennej i wprowadzamy indeks pierwszego elementu w tym obszarze, czyli ip.

Wewnątrz pętli sprawdzamy, czy indeksy i1 i i2 wskazują elementy podzbiorów. Jeśli któryś z nich wyszedł poza dopuszczalny zakres, to dany podzbiór jest wyczerpany - w takim przypadku do tablicy p przepisujemy elementy drugiego podzbioru.

Jeśli żaden z podzbiorów nie jest wyczerpany, porównujemy kolejne elementy z tych podzbiorów wg indeksów i1 i i2. Do tablicy p zapisujemy zawsze mniejszy z porównywanych elementów. Zapewnia to uporządkowanie elementów w tworzonym zbiorze wynikowym. Po zapisie elementu w tablicy p, odpowiedni indeks i1 lub i2 jest zwiększany o 1. Zwiększany jest również indeks i, aby kolejny zapisywany element w tablicy p trafił na następne wolne miejsce. Pętla jest kontynuowana aż do zapełnienia w tablicy p obszaru o indeksach od ip do ik.

Wtedy przechodzimy do końcowej pętli, która przepisuje ten obszar z tablicy p do tablicy wynikowej d. Scalane zbiory zostają zapisane zbiorem wynikowym, który jest posortowany rosnąco.

Specyfikacja algorytmu sortującego

Sortuj_przez_scalanie(d,ip, ik)

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków algorytmu sortującego

K01: is ←  (ip + ik + 1) div 2
K02: Jeśli is - ip > 1,
     to Sortuj_przez_scalanie(d, ip, is - 1)
K03: Jeśli ik - is > 0,
     to Sortuj_przez_scalanie(d, is, ik)
K04: Scalaj(d, ip, is, ik)
K05: Zakończ

Algorytm Sortowania przez Scalanie jest algorytmem rekurencyjnym. Wywołuje się go z zadanymi wartościami indeksów ip oraz ik. Przy pierwszym wywołaniu indeksy te powinny objąć całą tablicę d, zatem ip = 0, a ik = n-1.

Najpierw algorytm wyznacza indeks is, który wykorzystywany jest do podziału zbioru na dwie połówki:

• młodszą o indeksach elementów od ip do is - 1
• starszą o indeksach elementów od is do ik

Następnie sprawdzamy, czy dana połówka zbioru zawiera więcej niż jeden element. Jeśli tak, to rekurencyjnie sortujemy ją tym samym algorytmem.

Po posortowaniu obu połówek zbioru scalamy je za pomocą opisanej wcześniej procedury scalania podzbiorów uporządkowanych i kończymy algorytm. Zbiór jest posortowany.

Poniższy program jest programem z poprzedniego rozdziału, w którym sortowanie jest wykonywane nowym algorytmem.

// Sortowanie przez Scalanie

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

const int N = 100; // Liczba elementów do sortowania

int p[N]; // Tablica pomocnicza

// Funkcja scalająca
void Merge(int d[], int ip, int is, int ik)
{
    int i, i1, i2;

    i1 = ip;
    i2 = is;

    for(i = ip; i <= ik; i++)
    {
        if((i1 == is) || ((i2 <= ik) && (d[i2] < d[i1])))
            p[i] = d[i2++];
        else
            p[i] = d[i1++];
    }
    for(i = ip; i <= ik; i++) d[i] = p[i];
}

// Funkcja sortująca
void MergeSort(int d[], int ip, int ik)
{
    int is;

    is = (ip + ik + 1) / 2;
    if(is - ip > 1) MergeSort(d,ip,is-1);
    if(ik - is > 0) MergeSort(d,is,ik);
    Merge(d,ip,is,ik);
}

int main()
{
    srand(time(NULL));

    int t[N],i;

    for(i = 0; i < N; i++)
        t[i] = rand() % 1000;

    cout << "Przed:" << endl;
    for(i = 0; i < N; i++)
        cout << setw(4) << t[i];
    cout << endl << endl;

    // Sortowanie
    MergeSort(t,0,N-1);

    cout << "Po:" << endl;
    for(i = 0; i < N; i++)
        cout << setw(4) << t[i];
    cout << endl << endl;

    return 0;
}

Podsumowanie:

Do zapamiętania

• Scalanie zbiorów uporządkowanych.
• Algorytm sortowania przez scalanie.
• Własności sortowania przez scalanie

Algorytm Sortowania Szybkiego opiera się na strategii "dziel i zwyciężaj" (ang. divide and conquer), którą możemy krótko scharakteryzować w trzech punktach:

1. DZIEL - problem główny zostaje podzielony na podproblemy
2. ZWYCIĘŻAJ - znajdujemy rozwiązanie podproblemów
3. POŁĄCZ - rozwiązania podproblemów zostają połączone w rozwiązanie problemu głównego

Idea Sortowania Szybkiego jest następująca:

prof. Tony Hoare

Sortowanie Szybkie zostało wynalezione przez angielskiego informatyka, profesora Tony'ego Hoare'a w latach 60-tych ubiegłego wieku. W przypadku typowym algorytm ten jest najszybszym algorytmem sortującym z klasy złożoności obliczeniowej O(n·log n) - stąd pochodzi jego popularność w zastosowaniach. Musimy jednak pamiętać, iż w pewnych sytuacjach (zależnych od sposobu wyboru piwotu oraz niekorzystnego ułożenia danych wejściowych) klasa złożoności obliczeniowej tego algorytmu może się degradować do O(n²), co więcej, poziom wywołań rekurencyjnych może spowodować przepełnienie stosu i zablokowanie komputera. Z tych powodów algorytmu Sortowania Szybkiego nie można stosować bezmyślnie w każdej sytuacji tylko dlatego, iż jest uważany za jeden z najszybszych algorytmów sortujących - zawsze należy przeprowadzić analizę możliwych danych wejściowych właśnie pod kątem przypadku niekorzystnego.

Tworzenie partycji

Do utworzenia partycji musimy ze zbioru wybrać jeden z elementów, który nazwiemy piwotem. W lewej partycji znajdą się wszystkie elementy niewiększe od piwotu, a w prawej partycji umieścimy wszystkie elementy niemniejsze od piwotu. Położenie elementów równych nie wpływa na proces sortowania, zatem mogą one występować w obu partycjach. Również porządek elementów w każdej z partycji nie jest ustalony.

Jako piwot można wybierać element pierwszy, środkowy, ostatni, medianę lub losowy. Dla naszych potrzeb wybierzemy element środkowy:

Dzielenie na partycje polega na umieszczeniu dwóch wskaźników na początku zbioru - i oraz j. Wskaźnik i przebiega przez zbiór poszukując wartości mniejszych od piwotu. Po znalezieniu takiej wartości jest ona wymieniana z elementem na pozycji j. Po tej operacji wskaźnik j jest przesuwany na następną pozycję. Wskaźnik j zapamiętuje pozycję, na którą trafi następny element oraz na końcu wskazuje miejsce, gdzie znajdzie się piwot. W trakcie podziału piwot jest bezpiecznie przechowywany na ostatniej pozycji w zbiorze.

Przykład:

Dla przykładu podzielimy na partycje zbiór: { 7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3 }

 7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3 

 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 

 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
 i 
 j 

 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
   i 
 j 

 2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
   i 
   j 

 2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
     i 
   j 

 2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
     i 
     j 

 2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
         i 
     j 

 2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 
         i 
       j 

 2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 
           i 
       j 

 2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 
           i 
         j 

 2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 
             i 
         j 

 2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 
             i 
           j 

 2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 
                 i 
           j 

 2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 
                 i 
             j 

 2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 
                     i 
             j 

 2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 
                     i 
               j 

 2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 
                         i 
               j 

 2 4 3 1 4 3 3 2 7 8 7 9 6 6 7 6 5 
                         i 
                 j 

 2 4 3 1 4 3 3 2 5 8 7 9 6 6 7 6 7 
                 ^             i   
Lewa partycja    j   Prawa partycja

Po zakończeniu podziału na partycje wskaźnik j wyznacza pozycję piwotu. Lewa partycja zawiera elementy mniejsze od piwotu i rozciąga się od początku zbioru do pozycji j - 1. Prawa partycja zawiera elementy większe lub równe piwotowi i rozciąga się od pozycji j + 1 do końca zbioru. Operacja podziału na partycje ma liniową klasę złożoności obliczeniowej - O(n).

Algorytm Sortowania Szybkiego

Sortuj_szybko(d,lewy, prawy)

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

K01: i ← [(lewy + prawy) / 2]
K02: piwot ← d[i]
     d[i] ← d[prawy]
     j ← lewy
K03: Dla i = lewy, lewy + 1, ..., prawy - 1:
     wykonuj kroki K04...K05
K04:   Jeśli d[i] ≥ piwot,
       to kolejny obieg pętli K03
K05:   d[i] ↔ d[j]
       j ← j + 1
K06: d[prawy] ← d[j]
     d[j] ← piwot
K07: Jeśli lewy < j - 1,
     to Sortuj_szybko(d,lewy, j - 1)
K08: Jeśli j + 1 < prawy,
     to Sortuj_szybko(d,j + 1, prawy)
K09: Zakończ

Algorytm sortowania szybkiego wywołujemy podając za lewy indeks pierwszego elementu zbioru, a za prawy indeks elementu ostatniego (czyli Sortuj_szybko(d,0,n-1)). Zakres indeksów jest dowolny - dzięki temu ten sam algorytm może również sortować fragment zbioru, co wykorzystujemy przy sortowaniu wyliczonych partycji.

Na element podziałowy wybieramy element leżący w środku dzielonej partycji. Wyliczamy jego pozycję i zapamiętujemy ją tymczasowo w zmiennej i. Robimy to po to, aby dwukrotnie nie wykonywać tych samych rachunków.

Element d[i] zapamiętujemy w zmiennej piwot, a do d[i] zapisujemy ostatni element partycji. Dzięki tej operacji piwot został usunięty ze zbioru.

Ustawiamy zmienną j na początek partycji. Zmienna ta zapamiętuje pozycję podziału partycji.

W pętli sterowanej zmienną i przeglądamy kolejne elementy od pierwszego do przedostatniego (ostatni został umieszczony na pozycji piwotu, a piwot zapamiętany). Jeśli i-ty element jest mniejszy od piwotu, to trafia on na początek partycji - wymieniamy ze sobą elementy na pozycjach i-tej i j-tej. Po tej operacji przesuwamy punkt podziałowy partycji j.

Po zakończeniu pętli element z pozycji j-tej przenosimy na koniec partycji, aby zwolnić miejsce dla piwotu, po czym wstawiamy tam piwot. Zmienna j wskazuje zatem wynikową pozycję piwotu. Pierwotna partycja została podzielona na dwie partycje:

Sprawdzamy, czy partycje te obejmują więcej niż jeden element. Jeśli tak, to wywołujemy rekurencyjnie algorytm sortowania szybkiego przekazując mu granice wyznaczonych partycji. Po powrocie z wywołań rekurencyjnych partycja wyjściowa jest posortowana rosnąco. Kończymy algorytm.

Poniższy program jest programem z poprzedniego rozdziału, w którym sortowanie jest wykonywane nowym algorytmem.

// Sortowanie Szybkie

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

const int N = 200; // Liczba elementów do sortowania

// Funkcja sortująca
void QuickSort(int d[], int lewy, int prawy)
{
    int piwot, i, j;

    i = (lewy + prawy) / 2;

    piwot = d[i];
    d[i]  = d[prawy];
    j     = lewy;

    for(i = lewy; i <= prawy - 1; i++)
        if(d[i] < piwot)
        {
            swap(d[i],d[j]);
            j++;
        }
    d[prawy] = d[j];
    d[j] = piwot;

    if(lewy < j - 1)  QuickSort(d,lewy,j - 1);
    if(j + 1 < prawy) QuickSort(d,j + 1,prawy);
}

int main()
{
    srand(time(NULL));

    int t[N],i;

    for(i = 0; i < N; i++)
        t[i] = rand() % 1000;

    cout << "Przed:" << endl;
    for(i = 0; i < N; i++)
        cout << setw(4) << t[i];
    cout << endl << endl;

    // Sortowanie
    QuickSort(t,0,N-1);

    cout << "Po:" << endl;
    for(i = 0; i < N; i++)
        cout << setw(4) << t[i];
    cout << endl << endl;

    return 0;
}

Podsumowanie:

Do zapamiętania

• Zasada dziel i zwyciężaj.
• Tworzenie partycji.
• Algorytm Sortowania Szybkiego i jego własności.

1. Określamy zakres wartości, jakie mogą przyjmować elementy sortowanego zbioru. Niech w_min oznacza najmniejszą wartość, a w_max niech oznacza wartość największą.
2. Dla każdej możliwej wartości przygotowujemy kubełek-licznik, który będzie zliczał ilość wystąpień tej wartości w sortowanym zbiorze. Liczba liczników jest równa (w_max - w_min + 1). Każdy licznik jest początkowo ustawiony na wartość zero.
3. Przeglądamy kolejno elementy zbioru od pierwszego do ostatniego. Dla każdego elementu zbioru zwiększamy o jeden zawartość licznika o numerze odpowiadającym wartości elementu. W efekcie po przeglądnięciu wszystkich elementów zbioru liczniki będą zawierały ilość wystąpień każdej z możliwych wartości. Jeśli dany licznik zawiera 0, to wartość równa numerowi licznika w zbiorze nie występuje. Inaczej wartość ta występuje tyle razy, ile wynosi zawartość jej licznika.
4. Przeglądamy kolejne liczniki zapisując do zbioru wynikowego ich numery tyle razy, ile wynosi ich zawartość. Zbiór wyjściowy będzie posortowany.

Przykład:

Dla przykładu posortujemy opisaną wyżej metodą zbiór { 2 6 4 3 8 7 2 5 7 9 3 5 2 6 }.

Najpierw określamy zakres wartości elementów (w tym celu możemy na przykład wyszukać w zbiorze element najmniejszy i największy). U nas zakres wynosi:

wmin = 2,  wmax = 9

Potrzebujemy zatem:

wmax - wmin + 1 = 9 - 2 + 1 = 8 liczników.

Numer licznika określamy przy pomocy wzoru:

nn  = w - wmin
w – zliczana wartość

W ten sposób numery liczników będą zawsze rozpoczynały się od 0, co pozwoli umieścić je w kolejnych komórkach tablicy.

Liczniki ponumerujemy zgodnie z wartościami, które będą zliczały:

0

1

2

3

4

5

6

7

2

3

4

5

6

7

8

9

Na początku sortowania wszystkie liczniki mają stan zero:

0

1

2

3

4

5

6

7

2

3

4

5

6

7

8

9

0

0

0

0

0

0

0

0

Teraz przeglądamy kolejne elementy zbioru zliczając ich wystąpienia w odpowiednich licznikach (n_n  = w - w_min):

0

1

2

3

4

5

6

7

2

3

4

5

6

7

8

9

3

2

1

2

2

2

1

1

Przeglądamy kolejne liczniki począwszy od licznika o najmniejszym numerze (w przypadku sortowania malejącego przeglądanie rozpoczynamy od licznika o największym numerze, czyli od końca tablicy liczników) i zapisujemy do zbioru wynikowego tyle razy wartość w = n_n + w_min, ile wynosi zawartość licznika:

0

1

2

3

4

5

6

7

2

3

4

5

6

7

8

9

3

2

1

2

2

2

1

1

{ 2 2 2 3 3 4 5 5 6 6 7 7 8 9 }

Otrzymujemy zbiór posortowany.

Algorytm ma klasę złożoności obliczeniowej O(m + n), gdzie n oznacza liczbę elementów, a m oznacza liczbę ich wartości.

Algorytm Sortowania Kubełkowego

Dane wejściowe

Dane wyjściowe

Lista kroków

K01: Określ element najmniejszy wmin
     i największy wmax
K02: Utwórz dynamiczną tablicę liczników
     L o (wmax - wmin + 1) komórkach
K03: Wyzeruj komórki tablicy liczników L
K04: Dla i = 0,1,...,n - 1:
     wykonuj krok K05
K05:   Zwiększ o 1 L[T[i] - wmin]
K06: i ← 0
K07: Dla j = 0,1,...,wmax - wmin:
     wykonuj kroki K08...K11
K08:   Dopóki L[j] > 0:
       wykonuj kroki K09...K11
K09:     T[i]  ← j + wmin
K10:     L[j]  ← L[j] - 1
K11:     i  ← i + 1
K12: Usuń tablicę dynamiczną L
K13: Zakończ

Algorytm ma klasę czasowej złożoności obliczeniowej O(m + n), gdzie m oznacza ilość możliwych wartości, które mogą przyjmować elementy tablicy T, a n to ilość sortowanych elementów.

Poniższy program sortuje tablicę algorytmem sortowania kubełkowego. Przeanalizuj komentarze.

// Sortowanie Kubełkowe

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

const int N = 200; // Liczba elementów do sortowania

void BucketSort(int T[], int n)
{
    // Określamy el. najmniejszy i największy
    int i,wmax,wmin;
    wmax = wmin = T[0];
    for(i = 1; i < n; i++)
    {
      if(wmax < T[i]) wmax = T[i];
      if(wmin > T[i]) wmin = T[i];
    }

    // Tworzymy dynamicznie tablicę L
    int nL = wmax - wmin + 1;
    int * L = new int[nL];

    // Zerujemy liczniki
    for(i = 0; i < nL; i++) L[i] = 0;

    // Zliczamy elementy
    for(i = 0; i < n; i++)
        L[T[i] - wmin]++;

    // Przepisujemy zliczone elementy
    int j;
    i = 0;
    for(j = 0; j < nL; j++)
        while(L[j])
        {
            T[i++] = j + wmin;
            L[j]--;
        }
    // Usuwamy tablicę liczników
    delete [] L;
}

int main()
{
    srand(time(NULL));

    int T[N],i;

    int wmax = 999; // Maksymalny i minimalny
    int wmin = -99; // Zakres wartości
    
    // Generujemy tablicę do sortowania
    for(i = 0; i < N; i++)
        T[i] = wmin + rand() % (wmax - wmin + 1);

    // Wyświetlamy tablicę przed sortowaniem
    cout << "Przed:" << endl;
    for(i = 0; i < N; i++)
        cout << setw(4) << T[i];
    cout << endl << endl;

    // Sortujemy
    BucketSort(T,N);

    // Wyświetlamy tablicę po sortowaniu
    cout << "Po:" << endl;
    for(i = 0; i < N; i++)
        cout << setw(4) << T[i];
    cout << endl << endl;

    return 0;
}

Przed:
350 546 289 422 399  74 333 606 362 302 174 -94 264 -43 305 368 217 760 619 497
727 -32 -62 527 245 -71  71 275 651 240 931 339 319 751 560 -76 -32 410 507 -17
831  43 -93   7 -16 889 243 193 727 839  75 126 677 467  -9 263 -31 -72 763  -8
508 892 908 261 290 295 878 790 -81 872 797 748 -60 165 913 441 431 360 615 399
844 939 426 968 160 240 316  12 956 441 423 170 912  30  72 916 205 949 -74 878
782 860 401 310 261  45 758 819 472 470 -98 352 774 449 621 195 471 797 675 494
736 962 375  34 586 572 256 887 333 614 508 865 622   0 138 502 992 885 527 179
994 -44 602 541 646 -25 724 398  33 482  51 460 576   8 566  34 585 366 230 374
-34 609 758 862 216 940 654 983 758 221 335 585 911 174 647 182  16 853  34 593
587 350 753 278 857 521 874 140 283 577 384 903 517  87 531 294  74 162 425 -63

Po:
-98 -94 -93 -81 -76 -74 -72 -71 -63 -62 -60 -44 -43 -34 -32 -32 -31 -25 -17 -16
 -9  -8   0   7   8  12  16  30  33  34  34  34  43  45  51  71  72  74  74  75
 87 126 138 140 160 162 165 170 174 174 179 182 193 195 205 216 217 221 230 240
240 243 245 256 261 261 263 264 275 278 283 289 290 294 295 302 305 310 316 319
333 333 335 339 350 350 352 360 362 366 368 374 375 384 398 399 399 401 410 422
423 425 426 431 441 441 449 460 467 470 471 472 482 494 497 502 507 508 508 517
521 527 527 531 541 546 560 566 572 576 577 585 585 586 587 593 602 606 609 614
615 619 621 622 646 647 651 654 675 677 724 727 727 736 748 751 753 758 758 758
760 763 774 782 790 797 797 819 831 839 844 853 857 860 862 865 872 874 878 878
885 887 889 892 903 908 911 912 913 916 931 939 940 949 956 962 968 983 992 994

Podsumowanie:

Stabilność algorytmu kubełkowego zależna jest od implementacji (zobacz tutaj).

Do zapamiętania

• Algorytm Sortowania Kubełkowego i jego własności.