Implementacje i wykonanie badania algorytmów              5

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

1.  Temat

Przeanalizować i zbadać algorytmy sortowania metodą QuickSort, kubełkowego na bazie oraz metodą Shell’a.

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

2.1.         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ę”.

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

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

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

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

}

3.2.         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];

              }

}

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

   }

}

4.  Wyniki badania

Wyniki badania przedstawiono w tabelce:

Tabela 1. Rezultaty sortowania tablicy 100-elementowej.

* Liczba wywołań rekurencji

5.  Uwagi i wnioski z testowania i uruchamiania

a.             Każda z metod stosuje sortowanie in situ.

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

c.             Metoda kubełkowa wymaga zdecydowanie mniejszej liczby porównań od metody Shell’a.

d.            Zapotr...