Temat : Wybrane metody sortowania wewnętrznego.

Opracowali :

chodek

1. Cel ćwiczenia.

Ćwiczenia ma na celu zapoznanie studentów z wybranymi metodami sortowania wewnętrznego. Badane w ćwiczeniu metody sortowania to: sortowanie przez proste wstawianie, sortowanie przez proste wybieranie, sortowanie bąbelkowe, sortowanie szybkie(quick sort). Zakładamy, że długość tablicy podlegającej sortowaniu jest znana i wynosi n.

2. Metody sortowania:

2.1. Sortowanie przez proste wstawianie

Sortowanie przez proste wstawianie odbywa się w następujący sposób: dla każdego i = 2, 3,..., n trzeba powtarzać wstawianie a[i] w już uporządkowaną część tablicy a[l] <... <a[i-l].

W metodzie tej obiekty podzielone są umownie na dwa ciągi: ciąg wynikowy ai„.ai_i oraz ciąg źródłowy ai...an. W każdym kroku począwszy od i=2 i zwiększając i o jeden, i-ty element ciągu źródłowego przenosi się do ciągu wynikowego, wstawiając go w odpowiednim miejscu.

Algorytm:

1 Wykonaj co następuje począwszy od indeksu i=2 do i=n

2 Wskaż na i-ty element

3 Wstaw i-ty element w odpowiednim miejscy w a_i...a_t

2.2. Sortowanie przez proste wybieranie

Sortowanie przez proste wybieranie polega na wyznaczeniu najmniejszego elementu w ciągu zamianie go z pierwszym elementem w ciągu, wyznaczeniu najmniejszego elementu w a[2,n] i zamianie go z drugim elementem: wyznaczeniu najmniejszego elementu w a[3,n] i zamianie go z trzecim elementem itd. aż do posortowania całkowitego ciągu.

Algorytm:

1 Wykonaj co następuje n-1 razy (i=l do i=n-l)

2 Wskaż na najmniejszy element spośród a[i]...a[n];

3 Wymień go z a_t

2.3. Sortowanie bąbelkowe

Sortowanie bąbelkowe polega na przeglądaniu od końca sortowanej tablicy i zamianie

miejscami elementów jeśli są one w kolejności odwrotnej tj. pierwszy jest mniejszy od drugiego. Po zakończeniu pierwszego przejścia element najmniejszy powinien się znajdować na odpowiednim dla niego miejscu czyli na początku tablicy.

Algorytm:

1 Wykonaj co następuje n-1 razy (i=n-l,...,l)

2 Wskaż na ostatni element;

3 Wykonaj co następuje i razy

Porównaj wskazany element z elementem poprzednim Jeśli porównane elementy są w nie właściwej kolejności, zamień je miejscami Wskaż na następny element.

2.4. Szybkie sortowanie

Jest to metoda, w której stosuje się zasadę zamiany. W metodzie sortowania szybkiego

korzysta się z faktu, że w celu zapewnienia efektywności powinno się wymieniać obiekty położone daleko od siebie. Załóżmy że dane jest n obiektów ustawionych w odwrotnym porządku kluczy. Można posortować je wykonując tylko n/2 wymian, biorąc najpierw obiekty - skrajny z lewej strony i skrajny z prawej strony, a następnie posuwać się stopniowo do środka z obu stron. Oczywiście takie postępowanie możliwe jest tylko dlatego, że uporządkowanie było dokładnie odwrotne.

Wybierzmy losowo jakiś obiekt i nazwijmy go x; przeglądajmy tablicę od lewej strony aż znajdziemy obiekt a_i > x, a następnie przeglądajmy tablicę od prawej strony aż znajdziemy a_j < x. Wymieńmy teraz te dwa obiekty i kontynuujmy proces „przeglądania i zamiany", aż nastąpi spotkanie gdzieś w środku tablicy. W rezultacie otrzymamy tablicę podzieloną na lewą część z kluczami mniejszymi od x oraz prawą część z kluczami większymi od x. Jeżeli na przykład za x wybierzemy środkowy klucz 42, to w tablicy kluczy

44 55 12 42 94 6 18 67

trzeba dokonać dwóch wymian aby otrzymać tablicę podzieloną

18 6 12 42 94 55 44 67

Ostatnie wartości indeksów są i = 5 oraz j = 3. Klucze a_l...a_i-l są mniejsze bądź równe kluczowi x=42, klucze a_j+l...a_n są większe bądź równe temu kluczowi. Wynika stąd, że otrzymaliśmy podział na dwie części, a mianowicie ak.klucz x.klucz dla k=l...i-l

ak.klucz x.klucz dla k=j+l...n

oraz

ak.klucz = x.klucz dla k = j+l...i-l

Następnie powtarzamy tę operacje dla obu wcześniej utworzonych podciągów.

Algorytm

Istnieje ciąg liczb x_l, x_l+_l, x_p,

Kroki. Przyjmij za element podziału element v znajdujący się w pobliżu środka ciągu, i podziel tym elementem dany ciąg. Oznacza to, że v znajdzie się na pozycji elementu x_l dla pewnego k spełniającego l ≤k ≤ p, i elementy na lewo będą od niego nie większe a elementy na prawo od niego będą nie mniejsze.

Krok 2. Zastosuj ten sam algorytm do (l, k-1, x)

Krok 3. Zastosuj ten sam algorytm do (k+1, p, x)

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

Algorytmy te zaimplementowano w języku programowania C++, wykorzystaliśmy system wzorców 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. Poza tym do celów testowych powstały funkcje losujące, zapisujące, odczytujące oraz wypisujące wartości tablicy na ekranie. Poza tym zaimplementowano funkcje odmierzającą czas oraz wprowadzono makrodefinicje, które pozwalają wyłączyć zliczanie porównań oraz przypisań.

1. Funkcje pomocnicze

Wypisywanie zawartości zmiennej, zmienna T musi posiadać operator << wyjścia.

template<class T>

void printf_table(T& tab , int size)

{

int i;

for(i = 0 ; i < size ; i++)

std::cout << "tab[" << i << "] => "<< tab[i] << std::endl;

}

Funkcja zamieniająca zmienne wartościami, makro EQ_COUNTING pozwala zliczać ilość przypisań.

template<class T>

void swap(T& first ,T& sec)

{

T tmp = first;

first = sec;

sec = tmp;

#ifdef EQ_COUNTING

eq_counter++;

#endif

}

Funkcja wypełniająca tablice wartościami z przedziału <low , high), size - wielkość tablicy .

void rand_table(int * buf , int size , int low , int high)

{

srand((unsigned)time(NULL));

if (low == high) high++;

if (low < 0) high = abs(low) + high;

else high -= low;

int i;

for (i = 0 ; i < size; i++)

buf[i] = (rand() % high) + low;

}

Funkcja pozwalająca zapisać binarnie dane do pliku , gdzie file - nazwa pliku , size - wielkość tablicy.

void save_table(char * file, int * buf , int size)

{

FILE * fd = fopen(file , "wb");

assert(fd);

fwrite(buf , sizeof(int), size , fd);

fclose(fd);

}

Funkcja pozwalająca odczytać binarne dane z pliku , gdzie file - nazwa pliku , size - wielkość tablicy.

void open_table(char * file, int * buf , int size)

{

FILE * fd = fopen(file , "rb");

assert(fd);

fread(buf , sizeof(buf) , size , fd);

fclose(fd);

}

3.2. Funkcje sortujące.

• Quick sort

Implementacja iteracyjnej wersji quick sort-a, wykorzystano stos ze Standartowej Biblioteki Wzorców (STL) języka C++. Algorytm ten w przeciwieństwie do wersji rekurencyjnej nie jest ograniczony wielkością stosu oraz obciążeniem ponownego wywołania funkcji.

template<class T>

void quick_sort(T* tab, int size)

{

assert(size > 1);

std::stack<int> stc;

int i, j , iLow , iHigh;

T tmp;

RESET_INV_COUNTER;

stc.push(0);

stc.push(size - 1);

do {

iHigh = stc.top();

stc.pop();

iLow = stc.top();

stc.pop();

do {

i = iLow;

j = iHigh;

tmp = tab[(i+j)/2];

do {

while (tab[i] < tmp) {

i++;

INC_INV_COUNTER;

}

while (tab[j] > tmp) {

j--;

INC_INV_COUNTER;

}

if (i <= j ) {

swap(tab[i++] , tab[j--]);

}

} while(i < j);

if (i < iHigh) {

stc.push(i);

stc.push(iHigh);

}

iHigh = j;

} while(iLow < iHigh);

} while(!stc.empty());

}

• sortowanie bąbelkowe

size - wielkość tablicy

template<class T>

void bouble_sort(T& tab ,int size)

{

assert(size > 1);

RESET_INV_COUNTER;

int i, j;

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

for(j = size - 1; j > i ; j--)

if (tab[j-1] > tab[j]) {

swap(tab[j-1] , tab[j]);

INC_INV_COUNTER;

}

}

}

• sortowanie przez proste wstawianie

size - wielkość tablicy

template<class T>

void insertion_sort(T* tab , int size)

{

assert(tab && size > 1);

int i, j;

T tmp;

RESET_INV_COUNTER;

RESET_EQ;

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

tmp = tab[i];

INC_EQ_COUNTER;

for(j = i ; j > 0 ; j--) {

if(tab[j-1] > tmp) {

INC_INV_COUNTER;

INC_EQ_COUNTER;

tab[j] = tab[j-1];

}

else break;

}

tab[j] = tmp;

INC_EQ_COUNTER;

}

}

• sortowanie przez proste wybieranie

size - wielość tablicy

template<class T>

void selection_sort(T& tab , int size)

{

assert(size > 1);

int max;

int i, j;

RESET_INV_COUNTER;

RESET_EQ;

for(j = 1; j < size - 1 ; j++ ) {

max = j - 1;

for(i = j; i < size; i++)

if (tab[max] > tab[i]) {

max = i;

INC_INV_COUNTER;

}

swap(tab[j - 1], tab[max]);

}

}

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.

Poniższe wykresy przedstawiają porównania algorytmów sortowania dla prób losowo wygenerowanych danych od 2 do 100000 elementów.

Czas sortowania na podanej maszynie.

Ilość porównań w danym algorytmie.

Ilość przestawień w danym algorytmie. Jak widać na wykresie zmienna zliczająca ilość przestawień została przepełniona przez co mamy widoczne skoki na wykresie.

5.Wnioski.

• sortowanie bąbelkowe

wady :

a)złożoność O(n²)

b)duża ilość przypisań

c)duża ilość porównań

zalety:

a)prosty w implementacji

b)niezależnie od danych identyczna ilość porównań

Algorytm nie nadaje się do sortowania dużej ilości danych(za górną granice przyjęto 5000 elementów). Opcją dla tego algorytmu jest dopisanie warunku sprawdzenia czy w cyklu nie było zmiany, co pozwoli szybciej zakończyć działanie procedury.

-quick sort

wady:

1. trudny w implementacji

2. dla niekorzystnych danych złożoność może nawet spaść do O(n²)

3. rekurencyjna wersja tego algorytmu posiada ograniczenia wielkości stosu (wady rekurencji)

4. n²/6 - liczba zmian(w najgorszym przypadku)

5. trudność wyboru elementu dzielącego zbiór

zalety:

1. złożoność O(n log₂ n)

2. szybkość

3. n/6 - liczba zmian (w najlepszym przypadku)

4. zmienne pomocnicze mogą być trzymane w szybkich rejestrach maszyny cyfrowej

Jeżeli zależy nam na szybkości to możemy z powodzeniem zastosować ten algorytm , w najgorszym przypadku będziemy mieli złożoność sortowania bąbelkowego. Najkorzystniej było by podzielić zbiór tak , aby elementem dzielącym była mediana danego zbioru.

- sortowanie przez proste wstawianie

wady :

1. złożoność O(n²)

2. duża liczba porównań

zalety:

1. szybszy oraz bardziej efektywny od sortowania bąbelkowego

2. prosty w implementacji

3. dla danych posortowanych brak przestawień elementów

4. dla danych posortowanych odwrotnie najwięcej przestawień

5. zmienne pomocnicze mogą być trzymane w szybkich rejestrach maszyny cyfrowej

Algorytm prosty w implementacji, przez co może być wykorzystywany zamiast sortowania bąbelkowego.

- sortowanie przez proste wybieranie

wady:

1. złożoność O(n²)

2. duża ilość porównań

zalety:

1. szybszy od sortowania bąbelkowego

2. ilość przestawień n - 1

3. niezależnie od wartości danych identyczna liczba porównań

4. prosty w implementacji

Algorytm stosunkowo prosty w implementacji.

Ostatecznie przy odpowiednich danych wejściowych algorytm quick sort-a jest najszybszym, niemniej jednak w najgorszym przypadku spada jego złożoność do złożoności pozostałych algorytmów.

Przy małych zbiorach danych nie odczujemy większej różnicy przy wykorzystywaniu poszczególnych algorytmów, przy większej ilości danych zdecydowanie wybór pada na algorytm quick sort-a.

Niezależnie od rozpiętości wartości danych algorytmy będą działały tak samo.

Algorytmy sortowania bąbelkowego oraz sortowania przez proste wybieranie zostały opracowane tak że wartości elementu nie muszą być kopiowane do zmiennej pomocniczej , a jedynie znamy index w którym znajduje się dany element(np. wyszukanie wartości maksymalnej polega znalezieniu indexu pod którym znajduje się maksymalna wartość).

Literatura

http://www.i-lo.tarnow.pl/

http://www.programix.terramail.pl/alg_sort_quick.htm

http://4programmers.net

instrukcja do ćwiczenia

---