Opole, dn. 28 kwietnia 2004

Laboratorium Algorytmów i Struktur Danych

Temat:

Analiza algorytmów sortowania

Autor: Dawid Najgiebauer

Informatyka, sem. II, grupa lab. 11

czw. g. 16.20

Prowadzący: dr inż. Jan Sadecki

1. Temat

Przeanalizować i zbadać algorytmy sortowania przez zliczanie oraz sortowania przez indeksowanie.

2. Analiza, projektowanie

Celem badania jest sprawdzenie praktycznego zastosowania i efektywności badanych algorytmów sortujących.

Każdy z algorytmów będzie tworzył nową tablicę z posortowanymi wynikami. Dzięki temu tablica oryginalna nie ulegnie zniszczeniu.

1. Sortowanie przez zliczanie

Podstawowym założeniem tego algorytmu jest, że ma on zastosowanie wyłącznie do sortowania liczb całkowitych. Dla danego ciągu liczb tworzona jest pomocnicza tablica o długości odpowiadającej wartości największej z liczb ciągu nieposortowanego. Następnie w pozycje tej tablicy odpowiadające wartościom liczb wpisywana jest ilość ich wystąpień. Dla przykładowego ciągu (2, 5, 7, 0, 5, 10, 3, 2) tablica będzie wyglądać następująco:

Indeks:	0	1	2	3	4	5	6	7	8	9	10
Wartość:	1	0	2	1	0	2	0	1	0	0	1

Na podstawie tak utworzonej tablicy można już szybko stworzyć ciąg posortowany. W tym celu należy liczbę o wartości odpowiadającej wartości indeksu tablicy wpisać tyle razy, ile wskazuje wartość dla tego indeksu tej tablicy.

2. Sortowanie przez indeksowanie

Algorytm ten, w odróżnieniu od poprzedniego, pozwala sortować dowolne dane. Przy jego pomocy także możliwe jest bardzo szybkie stworzenie ciągu posortowanego wykorzystując do tego pomocniczą tablicę indeksów.

Tablica ta zawiera tylko i wyłącznie indeksy z tablicy nieposortowanej, a stworzenie posortowanego ciągu polega na wypisaniu elementów z tablicy pierwotnej zgodnie ze schematem stworzonym przez kolejne odczytywanie indeksów z tablicy indeksów. Kluczową rolą jest tutaj oczywiście prawidłowe umieszczenie właściwych numerów na właściwych miejscach w tablicy indeksu, co może być rozwiązane na wiele różnych sposobów. W zaproponowanym algorytmie określenie pozycji dla danego elementu polega na zliczeniu, ile występuje w ciągu elementów o wartości mniejszej od badanego.

3. Implementacje algorytmów

1. Implementacja algorytmu sortowania przez zliczanie

int *sort_zliczanie(int *tab, int n)

{

int max=0; //maksymalna wartosc, znajdujaca sie w tablicy

int x,z;

int *tabpom; //tablica pomocnicza zawierajaca liczbe wystapien danych liczb

int *posortowana; //tablica posortowana (posortowana - wskaznik)

for(x=0;x<n;x++)

if (max<tab[x]) max=tab[x];

tabpom=new int[max+1];

//Zerowanie tablicy:

for(x=0;x<=max;x++)

tabpom[x]=0;

for(x=0;x<n;x++)

tabpom[tab[x]]++;

posortowana=new int[n];

z=0;

for(x=0;x<=max;x++)

for(int y=1;y<=tabpom[x];y++)

{

posortowana[z]=x;

z++;

}

delete []tabpom;

return posortowana;

}

2. Implementacja algorytmu sortowania przez indeksowanie

int *sort_index(int *tab, int n)

{

int *index; //tablica indeksów

int *posortowana;

int a,b;

int poz_w_index;

index=new int[n];

for(a=0;a<n;a++)

{

poz_w_index=0;

for(b=0;b<n;b++)

{

if (tab[b]<tab[a]) poz_w_index++;

else if ((b<a) && (tab[b]==tab[a])) poz_w_index++;

}

index[poz_w_index]=a;

}

posortowana=new int[n];

for(a=0;a<n;a++)

posortowana[a]=tab[index[a]];

delete []index;

return posortowana;

}

4. Uwagi i wnioski z testowania i uruchamiania

1. Sortowanie poprzez zliczanie umożliwia wyłącznie sortowanie liczb całkowitych.

2. Sortowanie przez zliczanie ma zróżnicowane zapotrzebowanie na pamięć, które zależne jest wyłącznie od wartości maksymalnego elementu w ciągu; w przypadku częstych powtórzeń wykorzystanie pamięci do stworzenia tablicy umożliwiającej stworzenie ciągu posortowanego może być mniejsze niż sam ciąg, jednak w większości przypadków potrzeba jest dużo większy rozmiar na tablicę pomocniczą.

3. Sortowanie to nie modyfikuje ciągu bazowego.

4. Sortowanie przez indeksowanie umożliwia sortowanie dowolnych typów elementów z wykorzystaniem wielu różnych technik.

5. Rozmiar pomocniczej tablicy jest łatwy do przewidzenia i zajmuje rozmiar indeksu razy ilość pól w tablicy bazowej.

6. Sortowanie przez indeksowanie nie wprowadza modyfikacji do tablicy bazowej.

4 Dawid Najgiebauer

Uwagi i wnioski z testowania i uruchamiania 5

Temat 3

---