Opole, dn. 5 maja 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
Temat
Przeanalizować i zbadać algorytmy sortowania metodą QuickSort, kubełkowego na bazie oraz metodą Shell'a.
Analiza, projektowanie
Celem badania jest sprawdzenie praktycznego zastosowania i efektywności algorytmów sortujących.
Każdy z algorytmów będzie dokonywał modyfikacji na tej samej tablicy, jaka została mu zadana, a więc oryginalna tablica ulegnie zniszczeniu.
Sortowanie metodą QuickSort
Sortowanie to polega na podzieleniu danych na dwie części wg wartości średniej - mediany - która jest dobierana w sposób przypadkowy spośród analizowanego ciągu. Następnie następuje sortowanie obu części rekurencyjnie, przez zastosowanie tego samego algorytmu.
Podział następuje w taki sposób, że następuje wyszukiwanie wartości większej bądź równej wybranej idąc od lewej i zamiana jej z wartością mniejszą bądź równą wyszukując od prawej, aż do momentu, kiedy w wyniku takiego wyszukiwania analizowana pozycja z lewej i prawej strony „zejdą się”.
Sortowanie kubełkowe na bazie
Metoda ta polega na sortowaniu fragmentów danych - cyfr - od cyfry najmniej znaczącej do najbardziej znaczącej. W wersji kubełkowej zostaje utworzonych dziesięć „pojemników” odpowiadających cyfrom z zakresu 0 do 9, a następnie posortowanie - rozkład odpowiednich liczb do odpowiednich pojemników na podstawie analizowanej cyfry.
Po każdym takim podziale następuje analogiczny podział do kolejnej kolekcji „pojemników” na podstawie kolejnej z cyfr, jednak zachowując kolejność, w jakiej zostały dane liczby przydzielone do poprzednich pojemników, czyli na początku z pojemnika 0, następnie z 1 itd. i przy zachowaniu zasady kolejki FIFO w obrębie danego „pojemnika”.
Sortowanie metodą Shell'a
Algorytm Shellsort polega na wielokrotnym wykonaniu sortowania przez wstawianie. Jego parametrami są: ciąg kroków: k[1], k[2], ..., k[n] oraz tablica do posortowania.
Algorytm składa się z n faz. W i-tej fazie, za pomocą sortowania przez wstawianie są sortowane ciągi złożone z co k[i]-tego elementu tablicy.
Z założenia k[i]=k[i+1]*c+1, gdzie c jest stałą i przyjmuje się za nie najczęściej wartość 3. Założeniem jest także, że k[n]=1.
Implementacje i wykonanie badania algorytmów
Badania zostaną wykonane dla ciągów o długości 100. Każda z metod będzie bazowała na identycznej tablicy.
Dla każdej z metod zostanie zliczona całkowita ilość porównań przeprowadzonych w celu posortowania tablicy, a w przypadku metody QuickSort - liczbę wywołań rekurencji.
Implementacja algorytmu sortowania QuickSort
void qsort(int *tab, int l, int p)
{
wyw++;
if (l>=p) return;
int j = l;
int k = p;
int sv = tab[(p+l)/2];
while (j<=k)
{
while (tab[j]<sv) j++;
while (tab[k]>sv) k--;
if (j<k)
{
int temp=tab[j];
tab[j]=tab[k];
tab[k]=temp;
j++; k--;
}
else
if (j==k)
{
j++; k--;
}
}
qsort(tab, l, k);
qsort(tab, j, p);
}
Implementacja algorytmu sortowania kubełkowego na bazie
char GetColChar(int l, int poz)
{
return (char)((l/(int)pow(10,poz-1))-(l/(int)pow(10,poz))*10);
}
void basesort(int *tab, int n, int dl)
{
int *kubelki[10];
int indeksy[10];
int x,y,z,poz,nrkubla;
for(poz=1;wyw++,poz<=dl;poz++)
{
//Tworzenie kubelkow:
for(x=0;wyw++,x<10;x++)
{
kubelki[x]=new int[n];
indeksy[x]=0;
}
//Sortowanie wg poz. poz:
for(x=0;wyw++,x<n;x++)
{
nrkubla=GetColChar(tab[x],poz);
kubelki[nrkubla][indeksy[nrkubla]++]=tab[x];
}
//Złączanie:
z=0;
for(x=0;wyw++,x<10;x++)
for(y=0;wyw++,y<indeksy[x];y++)
tab[z++]=kubelki[x][y];
//Zwalnianie kubełkow:
for(x=0;wyw++,x<10;x++)
delete []kubelki[x];
}
}
Implementacja algorytmu sortowania Shell'a
void shellsort(int *tab,int n)
{
int h,i,j;
int t;
//Ustalenie h poczatkowego (max podzial na 9):
for(h=1;wyw++,h<=n/9;h=h*3+1);
while(wyw++,h>0)
{
for(i=h;wyw++,i<n;i++)
{
t=tab[i];
j=i-h;
while ((wyw++,j>=0) && (wyw++,tab[j]>t))
{
tab[j+h]=tab[j];
j-=h;
}
tab[j+h]=t;
}
h/=3;
}
}
Wyniki badania
Wyniki badania przedstawiono w tabelce:
Tabela 1. Rezultaty sortowania tablicy 100-elementowej.
Metoda: |
Liczba porównań: |
QuickSort |
169* |
Kubełkowe na bazie |
736 |
Shell'a |
1785 |
* Liczba wywołań rekurencji
Uwagi i wnioski z testowania i uruchamiania
Każda z metod stosuje sortowanie in situ.
Liczba wywołań funkcji QuickSort zależna jest zarówno od wielkości sortowanego ciągu, zawartym w nich elementów oraz doboru mediany - wartości, wg której następuje podział na dwa podciągi.
Metoda kubełkowa wymaga zdecydowanie mniejszej liczby porównań od metody Shell'a.
Zapotrzebowanie na pamięć w metodzie kubełkowej jest bardzo duże. Dodatkowo czas analizy jest wprost proporcjonalny do ilości baz.
6 Dawid Najgiebauer
Implementacje i wykonanie badania algorytmów 5
Temat 3