Informatyka dla klas II

Szybkie algorytmy sortujące

Sortowanie przez scalanie

Merge Sort

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

K01: Jeśli n < 2, silnia(n) ← 1 i zakończ
K02: silnia(n) ← n × silnia(n - 1) i zakończ

 

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.
 

Scalanie 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 }

 

Scalane
zbiory
Zbiór
tymczasowy
Opis wykonywanych działań
[1] 3  6  7  9 
 2  3  4  6  8 
 
Porównujemy ze sobą najmniejsze elementy scalanych zbiorów. Ponieważ zbiory te są już uporządkowane, to najmniejszymi elementami będą zawsze ich pierwsze elementy.
    3  6  7  9 
 2  3  4  6  8 
[1]
W zbiorze tymczasowym umieszczamy mniejszy element, w tym przypadku będzie to liczba 1. Jednocześnie element ten zostaje usunięty z pierwszego zbioru
    3  6  7  9 
[2]  4  6  8 
 1 
Porównujemy kolejne dwa elementy i mniejszy umieszczamy w zbiorze tymczasowym.
   [3] 6  7  9 
    3  4  6  8 
 1[2]
Następne porównanie i w zbiorze tymczasowym umieszczamy liczbę 3. Ponieważ są to elementy równe, to nie ma znaczenia, z którego zbioru weźmiemy element 3.
       6  7  9 
   [3] 4  6  8 
 1 2[3]
Teraz do zbioru tymczasowego trafi drugie 3.
       6  7  
      [4] 6  8 
 1 2 3[3]
W zbiorze tymczasowym umieszczamy mniejszy z porównywanych elementów, czyli liczbę 4.
      [6] 7  9 
          6  8 
 1 2 3 3[4]
Porównywane elementy są równe, zatem w zbiorze tymczasowym umieszczamy dowolny z nich.
          7  
         [6] 8 
 1 2 3 3 4[6]
Teraz drugą liczbę 6.
         [7] 
             8 
 1 2 3 3 4 6[6]
W zbiorze tymczasowym umieszczamy liczbę 7
             9 
            [8]
 1 2 3 3 4 6 6[7]
Teraz 8
            [9]
 1 2 3 3 4 6 6 7[8]
Drugi zbiór jest pusty. Od tego momentu już nie porównujemy, lecz wprowadzamy do zbioru tymczasowego wszystkie pozostałe elementy pierwszego zbioru, w tym przypadku będzie to liczba 9.

 1 2 3 3 4 6 6 7 8[9]
Koniec scalania. Zbiór tymczasowy zawiera wszystkie elementy scalanych zbiorów i jest uporządkowany. Możemy w dalszej kolejności przepisać jego zawartość do zbioru docelowego.

 

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.

 

Algorytm scalania dwóch zbiorów

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 }

 

Sortowany zbiór Opis wykonywanych operacji
d[0] d[1] d[2] d[3] d[4] d[5] d[6] d[7]
6 5 4 1 3 7 9 2 Zbiór wyjściowy.
6 5  4 1 3 7 9 2 Pierwszy podział.
6 5 4 1 3 7 9 2 Drugi podział
6 5 4 1 3 7 9 2 Trzeci podział.
5 6 1 4 3 7 2 9 Pierwsze scalanie.
1
4 5 6 2 3 7 9 Drugie scalanie.
1 2 3 4 5 6 7 9 Trzecie scalanie. Koniec.

 

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:

 

ip - indeks pierwszego elementu w młodszym podzbiorze
is - indeks pierwszego elementu w starszym podzbiorze
ik - indeks ostatniego elementu w starszym podzbiorze

 

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

 

pozostała część zbioru ip ... is ... ik pozostała część zbioru

młodszy podzbiór

starszy podzbiór

 

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:

Po pierwszym podziale prezentowanego powyżej zbioru otrzymujemy następujące wartości indeksów:

Młodsza
 połówka
Starsza
 połówka
ip = 0 is = 4
ik = 7

Po kolejnym podziale połówek otrzymujemy 4 ćwiartki dwuelementowe. Wartości indeksów będą następujące:

Młodsza połówka Starsza połówka
Młodsza
ćwiartka
Starsza
ćwiartka
Młodsza
ćwiartka
Starsza
ćwiartka
ip = 0 is = 2 ip = 4 is = 6
ik = 3 ik = 7

 

Specyfikacja algorytmu scalania

Scalaj(ip, is, ik)

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

 

Lista kroków algorytmu scalania

K01: i1ip;   i2is;   iip
K02: Dla i = ip, ip + 1, ..., ik: wykonuj
    jeśli (i1 = is) ∨ (i2ik  i d[i1] > d[i2]), to
        p[i] ← d[i2];   i2i2 + 1
    inaczej
        p[i] ← d[i1];   i1i1 + 1
K03: Dla i = ip, ip + 1,...,ik: d[i] ← p[i]
K04: Zakończ

 

Schemat blokowy algorytmu scalania

flow

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

 

Algorytm sortowania przez scalanie

Sortuj_przez_scalanie(ip, ik)

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

d[ ] - posortowany zbiór

Zmienne pomocnicze

is - indeks pierwszego elementu w starszym podzbiorze,  is N

 

Lista kroków algorytmu sortującego

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

 

Schemat blokowy algorytmu sortującego

flow

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ły zbiór 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.

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


 

 

Sortowanie przez kopcowanie
Heap Sort

Drzewo binarne

Dotychczas operowaliśmy na prostych strukturach danych, takich jak tablice. W tablicy elementy ułożone są zgodnie z ich numeracją, czyli indeksami. Jeśli za punkt odniesienia weźmiemy element d[i] (i = 2,3,..,n-1; n - liczba elementów w tablicy), to elementem poprzedzającym go będzie element o mniejszym o 1 indeksie, czyli d[i - 1]. Elementem następnym będzie element o indeksie o 1 większym, czyli d[i + 1]. Jest to tzw. hierarchia liniowa - elementy następują jeden za drugim. Graficznie możemy przedstawić to tak:

 

 

Pierwszy element d[0] nie posiada poprzednika (ang. predecessor - elementu poprzedzającego w ciągu). Ostatni element d[n-1] nie posiada następnika (ang. successor - elementu następnego w ciągu). Wszystkie pozostałe elementy posiadają poprzedniki i następniki.

Drzewo binarne jest hierarchiczną strukturą danych, którego elementy będziemy nazywali węzłami (ang. node) lub wierzchołkami. W hierarchii liniowej każdy element może posiadać co najwyżej jeden następnik. W drzewie binarnym każdy węzeł może posiadać dwa następniki (stąd pochodzi nazwa drzewa - binarny = dwójkowy, zawierający dwa elementy), które nazwiemy potomkami. dziećmi lub węzłami potomnymi danego węzła (ang. child node).

pic

Węzły są połączone krawędziami symbolizującymi następstwo kolejnych elementów w strukturze drzewa binarnego. Według rysunku po prawej stronie węzeł A posiada dwa węzły potomne: B i C. Węzeł B nosi nazwę lewego potomka (ang. left child node), a węzeł C nosi nazwę prawego potomka (ang. right child node).

Z kolei węzeł B posiada węzły potomne D i E, a węzeł C ma węzły potomne F i G. Jeśli dany węzeł nie posiada dalszych węzłów potomnych, to jest w strukturze drzewa binarnego węzłem terminalnym. Taki węzeł nosi nazwę liścia (ang. leaf node). Na naszym rysunku liśćmi są węzły terminalne D, E, F i G.

Rodzicem, przodkiem (ang. parent node) lub węzłem nadrzędnym będziemy nazywać węzeł leżący na wyższym poziomie hierarchii drzewa binarnego. Dla węzłów B I C węzłem nadrzędnym jest węzeł A. Podobnie dla węzłów D i E węzłem nadrzędnym będzie węzeł B, a dla F i G będzie to węzeł C.

Węzeł nie posiadający rodzica nazywamy korzeniem drzewa binarnego (ang. root node). W naszym przykładzie korzeniem jest węzeł A. Każde drzewo binarne, które zawiera węzły posiada dokładnie jeden korzeń.

 

Odwzorowanie drzewa binarnego

Jeśli chcemy przetwarzać za pomocą komputera struktury drzew binarnych, to musimy zastanowić się nad sposobem reprezentacji takich struktur w pamięci. Najprostszym rozwiązaniem jest zastosowanie zwykłej tablicy n elementowej. Każdy element tej tablicy będzie reprezentował jeden węzeł drzewa binarnego. Pozostaje nam jedynie określenie związku pomiędzy indeksami elementów w tablicy a położeniem tych elementów w strukturze drzewa binarnego.

Zastosujmy następujące odwzorowanie:

  • Element d[0] będzie zawsze korzeniem drzewa.
  • i-ty poziom drzewa binarnego wymaga 2i-1 węzłów. Będziemy je kolejno pobierać z tablicy.

Otrzymamy w ten sposób następujące odwzorowanie elementów tablicy w drzewo binarne:

 

pic

 

Dla węzła k-tego wyprowadzamy następujące wzory:

 

pic węzły potomne mają indeksy równe:
2k + 1 - lewy potomek
2k + 2 -
prawy potomek

węzeł nadrzędny ma indeks równy [(k - 1) / 2] (dzielenie całkowitoliczbowe)

 

Sprawdź, iż podane wzory są również spełnione w drzewach binarnych o większych rozmiarach niż prezentuje nasz przykład (pomocna może być kartka papieru).

 

Przykład:

Skonstruować drzewo binarne z elementów zbioru {7 5 9 2 4 6 1}

 

Operacja Opis
pic
7 5 9 2 4 6 1
Konstrukcję drzewa binarnego rozpoczynamy od korzenia, który jest pierwszym elementem zbioru, czyli liczbą 7.
pic
7 5 9 2 4 6 1
Do korzenia dołączamy dwa węzły potomne, które leżą obok w zbiorze. Są to dwa kolejne elementy, 5 i 9.
pic
7 5 9 2 4 6 1
Do lewego węzła potomnego (5) dołączamy jego węzły potomne. Są to kolejne liczby w zbiorze, czyli 2 i 4.
pic
7 5 9 2 4 6 1
Pozostaje nam dołączyć do prawego węzła ostatnie dwa elementy zbioru, czyli liczby 6 i 1. Drzewo jest kompletne.

 

Zrównoważone drzewa binarne

Umówmy się na potrzeby tego artykułu, iż binarne drzewo jest zrównoważone i uporządkowane, jeśli na wszystkich poziomach za wyjątkiem ostatniego posiada maksymalną liczbę węzłów, a na poziomie ostatnim węzły są ułożone kolejno od lewej strony. Innymi słowy, jeśli ostatni węzeł drzewa binarnego posiada numer i-ty, to drzewo zawiera wszystkie węzły od numeru 1 do i.

Warunek ten gwarantuje nam, iż każdy element tablicy będzie reprezentował pewien węzeł w drzewie binarnym - czyli w tej strukturze nie wystąpią dziury.

 

 

Drzewo po lewej stronie nie posiada węzła d[6]. Ale posiada wszystkie węzły od d[0] do d[5], jest zatem zrównoważone i uporządkowane. Można je bez problemu przedstawić za pomocą tablicy elementów od d[0] do d[5].

Drzewo po prawej stronie nie posiada węzła d[5]. Takiego drzewa nie przedstawimy poprawnie za pomocą tablicy elementów od d[0] do d[6], ponieważ nie mamy możliwości zaznaczenia (bez dodatkowych zabiegów), iż element d[5] nie należy do struktury drzewa. Zatem nie będzie to uporządkowane i zrównoważone drzewo binarne.

W uporządkowanych i zrównoważonych drzewach binarnych bardzo prosto można sprawdzić, czy k-ty węzeł jest liściem. Będzie tak, jeśli węzeł ten nie posiada węzłów potomnych. Zatem, jeśli drzewo binarne składa się z n węzłów, to wystarczy sprawdzić, czy 2k+1 > n-1. Jeśli tak, węzeł jest liściem. Jeśli nie, węzeł posiada potomka o indeksie 2k+1, zatem nie może być liściem.

 

Ścieżki na drzewach binarnych

Ścieżką nazwiemy ciąg węzłów drzewa binarnego spełniających warunek, iż każdy węzeł poprzedni jest rodzicem węzła następnego. Jeśli ścieżka składa się z k węzłów, to długością ścieżki jest liczba k - 1.

 

tree

 

Na powyższym rysunku zaznaczona została ścieżka biegnąca poprzez węzły {d[0], d[2], d[5], d[12]}. Ścieżka ta zawiera cztery węzły, ma zatem długość równą 3.

Wysokością drzewa binarnego nazwiemy długość najdłuższej ścieżki od korzenia do liścia. W powyższym przykładzie najdłuższa taka ścieżka ma długość 3, zatem zaprezentowane drzewo binarne ma wysokość równą 3.

Dla n węzłów zrównoważone drzewo binarne ma wysokość równą:

 

h = [log2n]

 

Podsumowanie nowej terminologii

węzeł  (ang. node)  -  element drzewa binarnego
rodzic, węzeł nadrzędny, przodek  (ang, parent node)  - węzeł leżący o 1 poziom wyżej w hierarchii
dziecko, potomek, węzeł potomny  (ang. child node)  - węzeł leżący o 1 poziom niżej w hierarchii, dla którego bieżący węzeł jest rodzicem.
korzeń drzewa  (ang. root node)  - pierwszy węzeł na najwyższym poziomie hierarchii, który nie posiada rodzica
liść, węzeł terminalny  (ang. leaf node)  - węzeł nie posiadający węzłów potomnych
ścieżka  (ang. path)  - droga na drzewie binarnym wiodąca poprzez poszczególne wierzchołki
 

Kopiec

Kopiec jest drzewem binarnym, w którym wszystkie węzły spełniają następujący warunek (zwany warunkiem kopca):

 

Węzeł nadrzędny jest większy lub równy węzłom potomnym (w porządku malejącym relacja jest odwrotna - mniejszy lub równy).

 

Konstrukcja kopca jest nieco bardziej skomplikowana od konstrukcji drzewa binarnego, ponieważ musimy dodatkowo troszczyć się o zachowanie warunku kopca. Zatem po każdym dołączeniu do kopca nowego węzła, sprawdzamy odpowiednie warunki i ewentualnie dokonujemy wymian węzłów na ścieżce wiodącej od dodanego węzła do korzenia.

 

Przykład:

Skonstruować kopiec z elementów zbioru {7 5 9 6 7 8 10}

Operacja Opis

7 5 9 6 7 8 10
Budowę kopca rozpoczynamy od pierwszego elementu zbioru, który staje się korzeniem.

7 5 9 6 7 8 10
Do korzenia dołączamy następny element. Warunek kopca jest zachowany.

7 5 9 6 7 8 10
Dodajemy kolejny element ze zbioru.
Po dodaniu elementu 9 warunek kopca przestaje być spełniony. Musimy go przywrócić. W tym celu za nowy węzeł nadrzędny wybieramy nowo dodany węzeł. Poprzedni węzeł nadrzędny wędruje w miejsce węzła dodanego - zamieniamy węzły 7 i 9 miejscami.
Po wymianie węzłów 7 i 9 warunek kopca jest spełniony.

7 5 9 6 7 8 10
Dołączamy kolejny element 6. Znów warunek kopca przestaje być spełniony - zamieniamy miejscami węzły 5 i 6.
Po wymianie węzłów 5 i 6 warunek kopca jest spełniony.

7 5 9 6 7 8 10
Dołączamy kolejny element 7. Warunek kopca przestaje obowiązywać. Zamieniamy miejscami węzły 6 i 7.
Po wymianie węzłów 6 i 7 warunek kopca obowiązuje.

7 5 9 6 7 8 10
Dołączamy kolejny węzeł. Powoduje on naruszenie warunku kopca, zatem wymieniamy ze sobą węzły 7 i 8.
Po wymianie węzłów 7 i 8 warunek kopca znów obowiązuje.

7 5 9 6 7 8 10
Dołączenie ostatniego elementu znów narusza warunek kopca. Zamieniamy miejscami węzeł 8 z węzłem 10.
Po wymianie węzłów 8 i 10 warunek kopca został przywrócony na tym poziomie. Jednakże węzeł 10 stał się dzieckiem węzła 9. Na wyższym poziomie drzewa warunek kopca jest naruszony. Aby go przywrócić znów wymieniamy miejscami węzły, tym razem węzeł 9 z węzłem 10.
Po wymianie tych węzłów warunek kopca obowiązuje w całym drzewie - zadanie jest wykonane.

 

Charakterystyczną cechą kopca jest to, iż korzeń zawsze jest największym (w porządku malejącym najmniejszym) elementem z całego drzewa binarnego.

 

Algorytm

Poniżej przedstawiamy algorytm konstrukcji kopca z elementów zbioru.

 

Specyfikacja problemu

Dane wejściowe

d[ ] - Zbiór zawierający elementy do wstawienia do kopca. Numeracja elementów rozpoczyna się od 1.
n - Ilość elementów w zbiorze,  n N

Dane wyjściowe

d[ ] - Zbiór zawierający kopiec

Zmienne pomocnicze

i - zmienna licznikowa pętli umieszczającej kolejne elementy zbioru w kopcu,  i N, i {2,3,...,n}
j,k - indeksy elementów leżących na ścieżce od wstawianego elementu do korzenia,  j,k C
x - zmienna pomocnicza przechowująca tymczasowo element wstawiany do kopca

 

Lista kroków

K01: Dla i = 1, ..., n-1: wykonuj K02...K05
K02:     ji;   k ← (j-1) div 2
K03:     x ← d[i]
K04:     Dopóki d[k] < x: wykonuj
        d[j] ← d[k]
        Jeśli k = 0, to idź do K05
        inaczej  jk; k(j-1) div 2
K05:     d[j] ← x
K06: Zakończ

Uwaga: przy porządku malejącym należy zmienić drugi warunek w kroku K04 z d[k] < x na d[k] > x.

 

Rozbiór kopca

Algorytm

W tym rozdziale nauczymy się rozbierać kopiec.  Zasada jest następująca:

  1. Zamień miejscami korzeń z ostatnim liściem, który wyłącz ze struktury kopca. Elementem pobieranym z kopca jest zawsze jego korzeń, czyli element największy.
  2. Jeśli jest to konieczne, przywróć warunek kopca idąc od korzenia w dół.
  3. Kontynuuj od kroku 1, aż kopiec będzie pusty.

Przykład:

Dokonaj rozbioru następującego kopca:


Operacja Opis

9
Rozbiór kopca rozpoczynamy od korzenia, który usuwamy ze struktury kopca. W miejsce korzenia wstawiamy ostatni liść.
   
Poprzednia operacja zaburzyła strukturę kopca. Idziemy zatem od korzenia w dół struktury przywracając warunek kopca - przodek większy lub równy od swoich potomków. Praktycznie polega to na zamianie przodka z największym potomkiem. Operację kontynuujemy dotąd, aż natrafimy na węzły spełniające warunek kopca.
 
8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
   W nowym kopcu przywracamy warunek kopca.
 
7 8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
    

W nowym kopcu przywracamy warunek kopca. W tym przypadku już po pierwszej wymianie węzłów warunek koca jest zachowany w całej strukturze.

   
5 7 8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
 

Przywracamy warunek kopca w strukturze.

 
4 5 7 8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
      

Przywracamy warunek kopca w strukturze.

    
2 4 5 7 8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem.
            
1 2 4 5 7 8 9
Po wykonaniu poprzedniej operacji usunięcia w kopcu pozostał tylko jeden element - usuwamy go. Zwróć uwagę, iż usunięte z kopca elementy tworzą ciąg uporządkowany.

 

Operację rozbioru kopca można przeprowadzić w miejscu. Jeśli mamy zbiór d[ ] ze strukturą kopca, to idąc od końca zbioru (ostatnie liście drzewa) w kierunku początku zamieniamy elementy z pierwszym elementem zbioru (korzeń drzewa), a następnie poruszając się od korzenia w dół przywracamy warunek kopca w kolejno napotykanych węzłach.

 

Specyfikacja problemu

Dane wejściowe

d[ ] - Zbiór zawierający poprawną strukturę kopca. Elementy są numerowane począwszy od 1.
n - Ilość elementów w zbiorze,  n N

Dane wyjściowe

d[ ] - Zbiór zawierający elementy pobrane z kopca ułożone w porządku rosnącym

Zmienne pomocnicze

i - zmienna licznikowa pętli pobierającej kolejne elementy z kopca,  i N, i {n-1,...,1}
j,k - indeksy elementów leżących na ścieżce w dół od korzenia,  j,k N
m - indeks większego z dwóch elementów potomnych, m N

 

Lista kroków

K01: Dla i = n - 1, n - 2, ..., 1: wykonuj K02...K08
K02:     d[0] ↔ d[i]
K03:     j ← 0;  k ← 1
K04:     Dopóki (k < i) wykonuj K05...K08
K05:         Jeżeli (k + 1 < i) ∧ (d[k + 1] > d[k]), to mk + 1
        inaczej  mk
K06:         Jeżeli d[m] ≤ d[j], to wyjdź z pętli K04 i kontynuuj następny obieg K01
K07:         d[j] ↔ d[m]
K08:         jmk2j + 1
K09: Zakończ

 

Sortowanie przez kopcowanie

Algorytm

Jeśli przeczytałeś uważnie poprzednie dwa rozdziały, to zasadę sortowania przez kopcowanie zrozumiesz od razu - w zbiorze tworzymy kopiec, a następnie dokonujemy jego rozbioru. W wyniku wykonania tych dwóch operacji zbiór zostanie posortowany.

 

Specyfikacja problemu

Dane wejściowe

d[ ] - Zbiór zawierający elementy do posortowania, które są numerowane począwszy od 0.
n - Ilość elementów w zbiorze,  n N

Dane wyjściowe

d[ ] - Zbiór zawierający elementy posortowane rosnąco

Zmienne pomocnicze i funkcje

Twórz_kopiec - procedura budująca kopiec z elementów zbioru d[ ]. Kopiec powstaje w zbiorze d[ ].
Rozbierz_kopiec - procedura dokonująca rozbioru kopca utworzonego w zbiorze d[ ]. Wynik rozbioru trafia z powrotem do zbioru d[ ].

 

Lista kroków

K01: Twórz_kopiec
K02: Rozbierz_kopiec
K03: Zakończ algorytm
Ponieważ sortowanie przez kopcowanie składa się z dwóch następujących bezpośrednio po sobie operacji o klasie czasowej złożoności obliczeniowej O(n log n), to dla całego algorytmu klasa złożoności również będzie wynosić O(n log n).

 

 

Sortowanie szybkie
Quick Sort

Algorytm

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:

 

DZIEL : najpierw sortowany zbiór dzielimy na dwie części w taki sposób, aby wszystkie elementy leżące w pierwszej części (zwanej lewą partycją) były mniejsze lub równe od wszystkich elementów drugiej części zbioru (zwanej prawą partycją).
ZWYCIĘŻAJ : każdą z partycji sortujemy rekurencyjnie tym samym algorytmem.
POŁĄCZ : połączenie tych dwóch partycji w jeden zbiór daje w wyniku zbiór posortowany.

 


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(n2), 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 - czasem lepszym rozwiązaniem może być zastosowanie wcześniej opisanego algorytmu sortowania przez kopcowanie, który nigdy nie degraduje się do klasy O(n2).

 

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:

 

piwot ← d[(lewy + prawy) div 2]  
piwot  - element podziałowy
d[ ] - dzielony zbiór
lewy - indeks pierwszego elementu
prawy  - indeks ostatniego elementu

 

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 }

 

Lp. Operacja Opis
1.
 7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3 
Wyznaczamy na piwot element środkowy.
2.
 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6
Piwot wymieniamy z ostatnim elementem zbioru
3.
 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 i 
 j 
Na początku zbioru ustawiamy dwa wskaźniki. Wskaźnik i będzie przeglądał zbiór do przedostatniej pozycji. Wskaźnik j zapamiętuje miejsce wstawiania elementów mniejszych od piwotu
4.
 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6   i 
 j 
Wskaźnikiem i szukamy elementu mniejszego od piwotu
5.
 2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6   i 
   j 
Znaleziony element wymieniamy z elementem na pozycji j-tej. Po wymianie wskaźnik j przesuwamy o 1 pozycję.
6.
 2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6     i 
   j 
Szukamy
7.
 2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6     i 
     j 
Wymieniamy i przesuwamy j.
8.
 2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6         i 
     j 
Szukamy
9.
 2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6         i 
       j 
Wymieniamy i przesuwamy j.
10.
 2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6           i 
       j 
Szukamy
11.
 2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6           i 
         j 
Wymieniamy i przesuwamy j.
12.
 2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6             i 
         j 
Szukamy
13.
 2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6             i 
           j 
Wymieniamy i przesuwamy j.
14.
 2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6                 i 
           j 
Szukamy
15.
 2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6                 i 
             j 
Wymieniamy i przesuwamy j.
16.
 2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6                     i 
             j 
Szukamy
17.
 2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6                     i 
               j 
Wymieniamy i przesuwamy j.
18.
 2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6                         i 
               j 
Szukamy
19.
 2 4 3 1 4 3 3 2 7 8 7 9 6 6 7 6                         i 
                 j 
Wymieniamy i przesuwamy j.
20.
 2 4 3 1 4 3 3 2 5 8 7 9 6 6 7 6 7 
                 ^             i   
Lewa partycja    j   Prawa partycja
Brak dalszych elementów do wymiany. Piwot wymieniamy z elementem na pozycji j-tej. Podział na partycje zakończony.

 

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).

Specyfikacja problemu

Sortuj_szybko(lewy, prawy)

Dane wejściowe

d[ ] - Zbiór zawierający elementy do posortowania. Zakres indeksów elementów jest dowolny.
lewy - indeks pierwszego elementu w zbiorze, lewy C
prawy - indeks ostatniego elementu w zbiorze, prawy C

Dane wyjściowe

d[ ] - Zbiór zawierający elementy posortowane rosnąco

Zmienne pomocnicze

piwot - element podziałowy
i, j - indeksy, i, j C

 

Lista kroków

K01:
i [  lewy + prawy  ]
2
K02: piwot ← d[i];   d[i] ← d[prawy];   jlewy
K03: Dla i = lewy, lewy + 1, ..., prawy - 1: wykonuj K04...K05
K04:     Jeśli d[i] ≥ piwot, to wykonaj kolejny obieg pętli K03
K05:     d[i] ↔ d[j];    jj + 1
K06: d[prawy] ← d[j];   d[j] ← piwot
K07: Jeśli lewy < j - 1, to Sortuj_szybko(lewy, j - 1)
K08: Jeśli j + 1 < prawy, to Sortuj_szybko(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(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.

 

Schemat blokowy

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:

 

partycja lewa od pozycji lewy do j - 1 zawiera elementy mniejsze od piwotu
partycja prawa od pozycji j + 1 do pozycji prawy zawiera elementy większe lub równe piwotowi.

 

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.

 

 

Sortowania o liniowej złożoności czasowej

Sortowanie kubełkowe
Bucket Sort

 

Opisany w tym rozdziale algorytm sortowania kubełkowego pozwala sortować zbiory liczb całkowitych - najlepiej o dużej ilości elementów, lecz o małym zakresie wartości. Zasada działania jest następująca:
  1. Określamy zakres wartości, jakie mogą przyjmować elementy sortowanego zbioru. Niech wmin oznacza najmniejszą wartość, a wmax 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 (wmax - wmin + 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 równym wartości elementu. Na przykład, jeśli kolejny element zbioru ma wartość 3, to zwiększamy licznik o numerze 3. 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.

 

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

 

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

 

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

 

[2:0] [3:0] [4:0] [5:0] [6:0] [7:0] [8:0] [9:0]

 

Teraz przeglądamy kolejne elementy zbioru zliczając ich wystąpienia w odpowiednich licznikach:

 

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

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

 

Zapis [2:3] oznacza, iż licznik numer 2 zawiera liczbę 3, a to z kolei oznacza, iż liczba 2 pojawiła się w zbiorze 3 razy. 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) i zapisujemy do zbioru wynikowego tyle razy numer licznika, ile wynosi jego zawartość:

 

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

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

 

Uwaga, pułapka:

Algorytm wymaga ponumerowania liczników kolejno od wmin do wmax. Niektóre języki programowania (np. C++) nie pozwalają numerować dowolnie elementów tablic - zwykle numeracja rozpoczyna się od liczby 0. W takich przypadkach musimy dokonać przeliczenia indeksu licznika, na zliczaną przezeń wartość i na odwrót. Wzory są na szczęście bardzo proste:

Mamy wartość w i chcemy znaleźć indeks licznika, który ją zlicza:

indeks ← w - wmin

Mamy indeks licznika i chcemy znaleźć zliczaną wartość w:

w ← indeks + wmin

 

Specyfikacja problemu

Dane wejściowe

n - liczba elementów w zbiorze, n N
d[ ] - sortowany zbiór liczb całkowitych. Indeksy elementów rozpoczynają się od 0.
wmin - minimalna wartość elementów zbioru,  wmin C
wmax - maksymalna wartość elementów zbioru,  wmax C

Dane wyjściowe

d[ ] - posortowany zbiór liczb całkowitych.

Zmienne pomocnicze

lw[ ] - tablica liczników wartości o indeksach od 0 do wmax - wmin. Każdy licznik przechowuje liczbę całkowitą
i, j - zmienne licznikowe pętli, i,j C

 

Lista kroków

K01: Dla i = 0, 1,...,wmax - wmin: wykonuj lw[i] ← 0
K02: Dla i = 0,1,...,n - 1: wykonuj lw[ d[i] - wmin] ← lw[ d[i] - wmin] + 1
K03: j ← 0
K04: Dla i = 0 , 1,...,wmax - wmin: wykonuj K05
K05:     Dopóki lw[i] > 0 wykonuj:

        d[j] ← i + wmin

        lw[i] ← lw[i] - 1

        jj + 1

K06: 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 zbioru, a n to ilość sortowanych elementów. Jeśli m jest małe w porównaniu z n (sortujemy dużo elementów o małym zakresie wartości), to na czas sortowania będzie miała wpływ głównie ilość elementów n i klasa złożoności uprości się do postaci O(n). Dzieje się tak dlatego, iż przy równomiernym rozkładzie dużej ilości elementów o małym zakresie wartości liczniki będą równomiernie zapełnione (stan każdego licznika będzie dążył do [n/m]). Zatem algorytm wykona:

  1. m operacji zerowania liczników - czas pomijalnie mały i przy dużym n nie wpływa istotnie na klasę algorytmu.
  2. n operacji zwiększania liczników
  3. n operacji przesłania numerów liczników do zbioru wynikowego - ilość pustych liczników będzie dążyła do zera.

W sytuacji odwrotnej, gdy sortujemy mało elementów o dużym zakresie wartości klasa złożoności zredukuje się z kolei do O(m) - spróbuj uzasadnić ten wynik samemu na podstawie analizy działania poszczególnych fragmentów algorytmu.

 

Sortowanie przez zliczanie
Counting Sort

Zasadę pracy algorytmu sortowania przez zliczanie jest najlepiej przedstawić za pomocą przykładu.

 

Przykład:

Posortować rosnąco zbiór danych:

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

Czynności wstępne

Dla każdej wartości w zbiorze przygotowujemy licznik i ustawiamy go na 0.

[0:0]  [1:0]  [2:0]  [3:0]  [4:0]  [5:0]  [6:0]  [7:0] [8:0]  [9:0]

Obieg zliczający

Przeglądamy kolejne elementy zbioru i zliczamy ich wystąpienia w odpowiednich licznikach. Np. element 6 powoduje zwiększenie o 1 licznika nr 6. Po wykonaniu tego obiegu w poszczególnych licznikach mamy ilość wystąpień każdej wartości. W naszym przykładzie otrzymamy:

[0:2]  [1:3]  [2:4]  [3:5]  [4:3]  [5:3]  [6:4]  [7:3] [8:4]  [9:3]

Teraz poczynając od drugiego licznika sumujemy zawartość licznika oraz jego poprzednika i otrzymujemy:

[0:2]  [1:5]  [2:9]  [3:14]  [4:17]  [5:20]  [6:24]  [7:27] [8:31]  [9:34]

W wyniku tej operacji w każdym liczniku otrzymaliśmy ilość wartości mniejszych lub równych numerowi licznika, które występują w zbiorze wejściowym. Na przykład:

[0:2] - w zbiorze wejściowym są dwie wartości 0
[1:5] - w zbiorze wejściowym jest pięć wartości mniejszych lub równych 1
[2:9] - w zbiorze wejściowym jest dziewięć wartość mniejszych lub równych 2, itd.

Zwróć uwagę, iż stan licznika określa teraz ostatnią pozycję minus 1 w zbiorze uporządkowanym, na której należy umieścić wartość równą numerowi licznika:


Wartość:  0 0 1 1 1 2 2 2 2 3 3 3 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 8 8 8 8 9 9 9
Pozycja:  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 28 29 30 31 32 33

 

Obieg dystrybucyjny

Przeglądamy jeszcze raz zbiór wejściowy idąc od ostatniego elementu do pierwszego (aby zachować stabilność sortowania). Każdy element umieszczamy w zbiorze wynikowym na pozycji równej zawartości licznika dla tego elementu. Po wykonaniu tej operacji licznik zmniejszamy o 1. Dzięki temu następna taka wartość trafi na wcześniejszą pozycję.

W naszym przykładzie rozpoczynamy od ostatniej liczby 3. Jej licznik ma zawartość [3:14]. Zatem liczbę 3 umieszczamy w zbiorze wynikowym na pozycji 14 - 1 = 13 i zmniejszamy o 1 stan licznika otrzymując [3:13]. Kolejna liczba 3 trafi teraz na pozycję 12, itd.

Dla liczby 5 stan licznika wynosi [5:20]. Umieszczamy ją zatem na 20 - 1 = 19 pozycji i licznik zmniejszamy o 1 otrzymując [5:19].

Postępujemy w ten sam sposób z pozostałymi elementami zbioru. W efekcie zbiór wynikowy będzie posortowany rosnąco:

 

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

 

Podsumowanie

Przyjrzawszy się dokładnie algorytmowi sortowania przez zliczanie możesz zastanawiać się, dlaczego postępujemy w tak dziwny sposób? Przecież mając zliczone wystąpienia każdej wartości w licznikach, możemy je od razu przepisać do zbioru wyjściowego, jak zrobiliśmy w algorytmie sortowania kubełkowego. Miałbyś rację, gdyby chodziło jedynie o posortowanie liczb. Jest jednak inaczej.

Celem nie jest posortowanie jedynie samych wartości elementów. Sortowane wartości są zwykle tzw. kluczami, czyli wartościami skojarzonymi z elementami, które wyliczono na podstawie pewnego kryterium Sortując klucze chcemy posortować zawierające je elementy. Dlatego do zbioru wynikowego musimy przepisać całe elementy ze zbioru wejściowego, gdyż w praktyce klucze stanowią jedynie część (raczej małą) danych zawartych w elementach. Zatem algorytm sortowania przez zliczanie wyznacza docelowe pozycje elementów na podstawie reprezentujących je kluczy, które mogą się wielokrotnie powtarzać. Następnie elementy są umieszczane na właściwym miejscu w zbiorze wyjściowym. Prześledź dokładnie podany poniżej algorytm oraz przykładowe programy, a wszystko powinno się wyjaśnić.

 

Specyfikacja problemu

Dane wejściowe

d[ ] - zbiór elementów do posortowania. Każdy element posiada pole klucz, wg którego dokonuje się sortowania. Pole klucz jest liczbą całkowitą. Indeksy elementów rozpoczynają się od 0.
n - ilość elementów w zbiorze d[ ]. n N
kmin - minimalna wartość klucza, kmin C
kmax - maksymalna wartość klucza, kmax C

Dane wyjściowe

b[ ] - zbiór z posortowanymi elementami ze zbioru d[ ]. Indeksy elementów rozpoczynają się od 0.

Zmienne pomocnicze

i - zmienna dla pętli iteracyjnych, i C
L[ ] - tablica liczników wartości kluczy. Elementy są liczbami całkowitymi. Indeksy przebiegają kolejne wartości od 0 do kmax - kmin .

 

Lista kroków

K01: Dla i = 0,1,...,kmax - kmin: wykonuj  L[i] ← 0
K02: Dla i = 0,2,...,n - 1: wykonuj L[d[i].klucz - kmin] ← L[d[i].klucz - kmin] + 1
K03: Dla i = 1, 2,...,kmax  - kminwykonuj L[i] ← L[i] + L[i - 1]
K04: Dla i = n - 1, n - 2,...,0: wykonuj K05...K06
K05:     b[ L[ d[i].klucz - kmin ]  - 1] ← d[i]
K06:     L[ d[i].klucz - kmin ] ← L[ d[i].klucz - kmin ] - 1
K07: Zakończ

 

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2018 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe