Informatyka dla klas II

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.

Przykład:

Jako przykład może posłużyć rekurencyjne obliczanie silni. Silnię liczby n należącej do zbioru liczb naturalnych definiujemy następująco:

n! = 1 × 2 × 3 × ... × (n - 1) × n

Na przykład: 5! = 1 × 2 × 3 × 4 × 5 = 120

Specyfikacja algorytmu

Dane wejściowe
n	- liczba, której silnie liczymy na danym poziomie rekurencyjnym,  n N
Dane wyjściowe
Wartość silni n!

Lista kroków

Przykładowy program w języku C++

// Rekurencyjne obliczanie silni
//------------------------------
// (C)2016 I LO w Tarnowie
// I LO w Tarnowie
//------------------------------

#include <iostream>

unsigned long long silnia(int n)
{
    if(n < 2) return 1;
    else return n * silnia(n - 1);
}

int main()
{
    unsigned n;

    cout << "Program oblicza rekurencyjnie silnie z liczby n\n"
            "-----------------------------------------------\n"
            "  (C)2016 mgr Jerzy Walaszek I LO w Tarnowie\n\n"
            "Podaj n = "; cin >> n;
    cout << endl << n << "! = " << silnia(n) << endl << endl;

    return 0;
}

Dzięki rekurencji funkcja wyliczająca wartość silni staje się niezwykle prosta. Najpierw sprawdzamy warunek zakończenia rekurencji, tzn. sytuację, gdy wynik dla otrzymanego zestawu danych jest oczywisty. W przypadku silni sytuacja taka wystąpi dla n < 2 - silnia ma wartość 1. Jeśli warunek zakończania rekurencji nie wystąpi, to wartość wyznaczamy za pomocą rekurencyjnego wywołania obliczania silni dla argumentu zmniejszonego o 1. Wynik tego wywołania mnożymy przez n i zwracamy jako wartość silni dla n.

Wynaleziony w 1945 roku przez Johna von Neumanna algorytm sortowania przez scalanie 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.
 

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:

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]

Z podanego przykładu możemy wyciągnąć wniosek, iż operacja scalania dwóch uporządkowanych zbiorów jest dosyć prosta. Diabeł jak zwykle tkwi w szczegółach.

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 literką 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:

Scalaj(i_p, i_s, i_k)

Dane wejściowe

d[ ]	- scalany zbiór
ip	- indeks pierwszego elementu w młodszym podzbiorze,  ip N
is	- indeks pierwszego elementu w starszym podzbiorze,  is N
ik	- indeks ostatniego elementu w starszym podzbiorze,  ik N

Dane wyjściowe

d[ ]	- scalony zbiór

Zmienne pomocnicze

p[ ]	- zbiór pomocniczy, który zawiera tyle samo elementów, co zbiór d[ ].
i1	- indeks elementów w młodszej połówce zbioru d[ ],  i1 N
i2	- indeks elementów w starszej połówce zbioru d[ ],  i2 N
i	- indeks elementów w zbiorze pomocniczym p[ ],  i N

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 zbioru d[ ]. W tablicy p algorytm będzie tworzył zbiór tymczasowy, który po zakończeniu scalania zostanie przepisany do zbioru d[ ] w miejsce dwóch scalanych podzbiorów.

Parametrami wejściowymi do algorytmu są indeksy i_p, i_s oraz i_k, 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 i₁ (młodszy podzbiór od pozycji i_p do i_s - 1) oraz i₂ (starszy podzbiór od pozycji i_s do i_k). 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 i_p do i_k, 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 i_p.

Wewnątrz pętli sprawdzamy, czy indeksy i₁ i i₂ 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 i₁ i i₂. 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 i₁ lub i₂ 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 i_p do i_k.

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.

Dane wejściowe

d[ ]	- sortowany zbiór
ip	- indeks pierwszego elementu w młodszym podzbiorze,  ip N
ik	- indeks ostatniego elementu w starszym podzbiorze,  ik N

Dane wyjściowe

Zmienne pomocnicze

is	- indeks pierwszego elementu w starszym podzbiorze,  is N

Algorytm sortowania przez scalanie jest algorytmem rekurencyjnym. Wywołuje się go z zadanymi wartościami indeksów i_p oraz i_k. Przy pierwszym wywołaniu indeksy te powinny objąć cały zbiór d, zatem i_p = 0, a i_k = n-1.

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

- młodszą o indeksach elementów od i_p do i_s - 1
- starszą o indeksach elementów od i_s do i_k

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.

W przykładowych programach procedurę scalania umieściliśmy bezpośrednio w kodzie algorytmu sortującego, aby zaoszczędzić na wywoływaniu.