Temat : Wybrane metody sortowania wewnętrznego.

Opracował :

chodek

1. Cel ćwiczenia.

Ćwiczenie ma na celu zapoznanie studentów z wybranymi metodami sortowania. Badane w ćwiczeniu metody sortowania to : sortowanie stogowe oraz sortowanie przez scalanie.

2. Metody sortowania wstęp teoretyczny.

2.1. Sortowanie stogowe.

Wstęp

Drzewo binarne to drzewiasta struktura danych, w której liczba potomków każdego węzła (rodzica) wynosi nie więcej niż dwa. Wyróżnia się wtedy lewego i prawego potomka danego węzła.

Drzewo binarne, w którym liczba potomków każdego węzła wynosi albo zero albo dwa, nazywane jest drzewem regularnym.

Aby dowolną n-elementową tablicę H (indeksowaną od 1 do n) o elementach  h1,h2, .., h_n traktować jak drzewo binarne należy przyjąć, że

• korzeń drzewa stanowi pierwszy element tablicy - element o indeksie 1,

• drzewo powstaje z zależności, że element hi, i < n div 2 stanowi rodzica dla elementów h_2*1 i 2_2*i+1
  

Stóg (kopiec) (ang. heap) to drzewo binarne o następujących cechach:

• dla wszystkich potomków wartości węzła są w stałej relacji mniejszości z wartością rodzica - tą własność nazywa
  się własnością stogu (kopca),

• drzewo jest prawie pełne tzn. liście (elementy bez potomków) występują na ostatnim i ewentualnie przedostatnim
  poziomie drzewa,

• liście na ostatnim poziomie są ściśle ułożone od lewej do prawej.

Dla przyjętej relacji mniejszości, między wartością potomka a wartością rodzica, w korzeniu kopca znajdzie się węzeł o największej wartości.

Dla drzewa definiuje się operacje :

• znajdowania indeksu lewego potomka od i
  left(i) = 2 * i

• znajdowania indeksu prawego potomka od i
  right(i) = 2 * i + 1

• znajdowania indeksu rodzica od i

parent(i) = i div 2

Powyższe operacje będą przydatne przy procesie sortowania

Sortowanie

Złożoność tego algorytmu to O(nlog(n)). Sortowanie stogowe zadanej tablicy H odbywa się niejako dwuetapowo. W pierwszym etapie z H traktowanej jak drzewo binarne tworzy się stóg. Drugi etap jest procesem iteracyjnym - polega na zabezpieczeniu elementu największego i następnie przywróceniu własności stogu.

2.2. Sortowanie przez scalanie.

Scalanie dwóch ciągów uporządkowanych w jeden ciąg uporządkowany może być wykonane w bardzo prosty spo­sób: patrzymy na początki danych ciągów i do tworzonego ciągu przenosimy mniejszy z elementów czołowych lub którykolwiek z ciągów. Kolejność przenoszenia elementów z ciągów do ciągu uporządkowanego zależy od ich wartości, które mogą powo­dować, że jeden z ciągów będzie znacznie prędzej przeniesiony niż drugi. Algorytm scalania dwóch ciągów uporządkowanych:

Dane : Dwa ciągi uporządkowane x oaz y.

Wyniki: Uporządkowany ciąg wyjściowy z.

Krok 1: Dopóki oba ciągi x i y nie są puste wykonuj co następuje: Przenieś najmniejszy z elementów ciągów x i y do ciągu z.

Krok 2: Do końca ciągu z dopisz elementy pozostałe w jednym z ciągów x lub y.

Algorytm scalania dwóch uporządkowanych ciągów można zastosować do tworzenia uporządkowanego ciągu z podcią­gów już uporządkowanych. A czy można go zastosować do porządkowania dowolnych ciągów? Tak - jeśli potrafimy je najpierw uporządkować. A czy można je uporządkować tą samą metodą? Można. Dochodzimy w ten sposób do metody porządkowania ciągu, która na zasadzie dziel i zwyciężaj, scala dwa prawie równoliczne podciągi, uporządkowane tą samą metodą.

Ciąg jest dzielony w każdym kroku na dwa niemal równoliczne podciągi, które rekurencyjnie porządkowane są tą sama metodą. Warunkiem zakończenia rekurencji w tym algorytmie jest sytuacja kiedy ciąg ma tylko jeden element. Zatem powrót z wywołań rekurencyjnych rozpoczyna się z ciągami złożonymi z pojedynczych elementów, które są następnie scalane w ciągi o długości dwa, a następnie w ciągi o długości trzy lub cztery elementy itd.

Algorytm porządkowania przez scalanie:

Dane: Ciąg liczb xl, x_l+1,..., x_p.

Wynik: Uporządkowanie ciągu od najmniejszej do największej.

Krok 1: Przyjmij s := (l + p) div 2 i wykonaj co następuje

Krok 2: Zastosuj ten sam algorytm dla (l, s, x).

Krok 3: Zastosuj ten sam algorytm dla (s + l,p,x).

Krok 4: Zastosuj algorytm scalania do powstałych ciągów.

3 . Przykłady implementacji powyższych algorytmów

Algorytmy zaimplementowano w języku programowania C++, wykorzystano system wzorców tegoż języka co daje nam możliwość wykorzystania poszczególnych algorytmów z typami danych które udostępniają operator [] oraz operator porównania <. Poza tym wszystkie algorytmy „zamknięto” w przestrzeni nazw algo aby nazwy funkcji nie kolidowały. Do celów testowych powstały funkcje losujące, zapisujące, odczytujące oraz wypisujące wartości tablicy na ekranie. Napisano funkcje odmierzającą czas oraz wprowadzono makrodefinicje, które pozwalają wyłączyć zliczanie porównań oraz przypisań.

Funkcje oraz makra pomocnicze:

1. odmierzanie czasu plik nagłówkowy <mtime.h>

make_time - konwersja zmiennej „czasowej” do postaci łańcucha znaków, START_TIMER - włączanie zliczania , STOP_TIMER - zakończenie zliczania, GET_TIMER - pobranie zmiennej timera.

2. zliczanie przypisań plik nagłówkowy <extra.h>

RESET_EQ - zerowanie licznika przypisań, INC_EQ_COUNTER - inkrementacja licznika przypisań , GET_INC_COUNTER - pobranie zmiennej licznika

3. zliczanie porównań plik nagłówkowy <extra.h>

RESET_INV_CONTER - zerowanie licznika porównań, INC_INV_COUNTER - inkrementacja licznika porównań, GET_INV_COUNTER - pobranie zmiennej licznika

4. funkcje dodatkowe plik nagłówkowy <extra.h> oraz <add.h>

printf_table - wypisanie zawartości tablicy , swap - zamian wartości argumentów, rand_table - generowanie losowej tablicy liczb, save_table - zapisanie tablicy , open_table - odczyt tablicy

W poniższych funkcjach zastosowano identyfikatory :

tab = jest to sortowana tablica

size = wielkość sortowanej tablicy

step = (algorytm sortowania prze scalanie) wielkość posortowanych już podciągów

Wszystkie definicje funkcji sortowania znajdują się w pliku nagłówkowym <asort.h>

3.1. Algorytm tworzenia stogu.

Zaimplementowano dwa algorytmy tworzenia stogu do „góry” oraz do „dołu”.

Tworzenie stogu do „dołu” :

template<class T>

void make_heap_down(T& tab , int size)

{

assert(size > 1);

int i, node, parent;

RESET_INV_COUNTER;

RESET_EQ;

for (i = 1 ; i < size ; i++) {

node = i;

parent = (node - 1) / 2;

while(parent > 0 && tab[node] > tab[parent]) {

INC_INV_COUNTER;

swap(tab[node], tab[parent]);

node /= 2;

parent = (node - 1) / 2;

}

}

}

Tworzenie stogu do „góry”:

template<class T>

void make_heap_up(T& tab , int size)

{

assert(size > 1);

int parent = size / 2;

int node, tnode;

RESET_INV_COUNTER;

RESET_EQ;

do {

parent--;

node = parent * 2 + 1;

if (node + 1 < size) {

if (tab[node] < tab[node + 1]) node++;

INC_INV_COUNTER;

}

if (tab[parent] < tab[node]) {

INC_INV_COUNTER;

swap(tab[parent] , tab[node]);

tnode = 2 * node + 1;

while (tnode < size) {

if (tnode + 1 < size) {

if (tab[tnode] < tab[tnode + 1]) tnode++;

INC_INV_COUNTER;

}

if (tab[node] < tab[tnode]) {

INC_INV_COUNTER;

swap(tab[node] , tab[tnode]);

node = tnode;

}

else break;

tnode = 2 * node + 1;

}

}

} while (parent > 0) ;

}

3.2. Algorytm sortowanie stogu.

template<class T>

void sort_heap(T& tab , int size)

{

int last = size - 1;

int parent;

int node;

RESET_INV_COUNTER;

RESET_EQ;

while (last > 0) {

swap(tab[0] , tab[last]);

parent = 0;

node = parent * 2 + 1;

while (node < last) {

if (node + 1 < last) {

if (tab[node] < tab[node + 1]) node++;

INC_INV_COUNTER;

}

if (tab[parent] < tab[node]) {

INC_INV_COUNTER;

swap(tab[parent] , tab[node]);

parent = node;

}

else break;

node = parent * 2 + 1;

}

last--;

}

}

3.3. Algorytm scalania dwóch ciągów.

template<class T>

void merge(T* first ,int fsize ,T* sec ,int ssize ,T* tab)

{

int i, ifirst = 0;

int isec = 0;

for (i = 0 ; i < fsize + ssize; i++) {

if (first[ifirst] < sec[isec]) {

INC_INV_COUNTER;

INC_EQ_COUNTER;

tab[i] = first[ifirst++];

if (ifirst >= fsize)

while (isec < ssize) {

tab[++i] = sec[isec++];

INC_EQ_COUNTER;

}

}

else {

tab[i] = sec[isec++];

INC_EQ_COUNTER;

if (isec >= ssize)

while(ifirst < fsize) {

tab[++i] = first[ifirst++];

INC_EQ_COUNTER;

}

}

}

}

3.3. Algorytm sortowania przez scalanie.

template<class T>

void merge_sort(T* tab, int size, int step = 1)

{

assert(size > 1 && step > 0); //parzysty przedzial

RESET_INV_COUNTER;

RESET_EQ;

T* pFin = new T[size];

assert(pFin);

T* pTmp = tab;

T* pPos;

int part, i, rest;

while (size > step) {

part = 2 * step;

pPos = pFin;

rest = size - (size % part);

for(i = 0 ; i < rest ; i += part)

merge(pTmp + i , step , pTmp + step + i,step , pPos + i);

if (size % part > step) {

merge(pTmp + i , step , pTmp + step + i, size % step, pPos + i);

}

else {

for(rest = 0 ; rest < size % part ; rest++) {

pPos[i + rest] = pTmp[i + rest];

INC_EQ_COUNTER;

}

}

step *= 2;

pFin = pTmp;

pTmp = pPos;

}

if (pPos != tab) {

for(i = 0 ; i < size; i++) tab[i] = pPos[i];

delete pPos;

}

else delete pFin;

}

4. Wyniki przeprowadzonych doświadczeń.

Wszystkie badania zostały przeprowadzone na komputerze o następujących parametrach technicznych:

Procesor AMD Duron 1400@2000Mhz

Płyta główna EPOX 8RDA3

Pamięci Kingston DDR400 512MB

Powyższy komputer pracuje pod kontrolą systemu Windows XP Profesional.

Wszystkie próby przeprowadzono dla tych samych danych wejściowych dla każdego algorytmu, próby przeprowadzano na seriach od 100 000 do 10 000 000 elementów typu int o wielkości 4 bajtów(całkowita wielkość danych tj. ≈38MB).

1. Tworzenie stogu.

Dla lepszego porównania zrobiono testy na algorytmie tworzenia stogu zawartego w bibliotece standartowej wzorców (STL) języka C++.

Algorytmy tworzenia stogu:

Czas wykonania algorytmu:

Ilość porównań :

Ilość przypisań:

Algorytmy sortowania:

Czas wykonania algorytmów:

Wykresy od danych posortowanych oraz odwrotnie posortowanych przedstawiają się identycznie dlatego też nie umieszczono dodatkowych wykresów.

5.Wnioski.

Sortowanie stogowe :

zalety:

1. złożoność rzędu O(n log₂ n)[2]

2. brak zapotrzebowania na dodatkową pamięć

3. już zaimplementowane w STL(stl::sort_heap i stl::make_heap)

wady:

1. skomplikowana implementacja

2. stosunkowo duża liczba porównań(w stosunku do sortowania przez scalanie)

Sortowanie przez scalanie:

zalety:

1. złożoność rzędu O(n log₂ n)[1]

2. mała liczba porównań

wady:

1. skomplikowana implementacja

2. duże zapotrzebowanie pamięci(wielkość sortowanej tablicy w przypadku algorytmu przedstawionego w przykładzie)

Sortowanie stogowe zostało podzielone na dwa etapy :

budowanie stogu , w zasadzie jest to funkcja która jest zależna od rozłożenia danych, okazało się że procedury które napisałem działają najszybciej dla danych posortowanych odwrotnie. Aczkolwiek trzeba zaznaczyć że budowanie kopca zabiera do 20% czasu sortowania całego zbioru. Funkcja make_heap z biblioteki standartowej działa niezależnie od danych. Przeprowadzono porównania dla dwóch funkcji tworzących stóg do dołu oraz do góry nieznacznie szybsza (make_heap_down). Ilośc porównań dla procedury tworzenia stogu do „góry” jest zdecydowanie niższa. Ilość przypisań dla procedury tworzenia stogu do „dołu” jest mniejsza.

sortowanie stogu - okazało się iż funkcja z biblioteki standartowej języka C++ była ok. 40% szybsza. Stąd wniosek że należało by zoptymalizować moją funkcje.

Im większe posortowane bloki danych w sortowaniu przez scalanie tym szybciej działa algorytm.

Okazało się iż algorytm ten działa najszybciej dla danych losowych, najprawdopodobniej spowodowane jest to największą ilością porównań w algorytmie w takiej sytuacji.

Dla testowanych danych algorytm sortowania przez scalanie zrobił to w najkrótszym czasie, lecz należy przy tym pamiętać że algorytm ten sortował dane już częściowo posortowane co skutecznie przyspieszyło działanie całego algorytmu.

W przypadku częściowo posortowanych danych słusznym posunięciem będzie sortowanie danych algorytmem przez scalanie.

W przypadku ograniczeń pamięciowych należy pominąć algorytm przez scalanie ponieważ wykorzystuje on w znaczny sposób pamięć operacyjną komputera.

Okazuje się iż przedstawione algorytmy są dużo szybsze od prostych algorytmów sortowania ( bouble sort , insertion sort , selection sort itp.) dlatego warto wykorzystać standartowe funkcje języka programowania (C++) , tutaj mam na myśli bibliotekę standartową i funkcje std::make_heap oraz std::sort_heap, okazuje się iż algorytmy tam zawarte zostały bardzo dobrze zaimplementowane.

Literatura

[1] http://www.i-lo.tarnow.pl/

[2] „Wprowadzenie do algorytmów” Thomas. H. Cormen , Charles E. Leiserson , Ronald L. Rivest

[3] instrukcja do zadania

---