Strona główna » Algorytmy » Sortowanie » Sortowanie Grzebieniowe
 

Sortowanie Grzebieniowe

https://mattomatti.com/fs05

O sortowaniu

Sortowanie Grzebieniowe (ang. combsort) opiera się na idei sortowania bąbelkowego. Różnica jednak polega na wykonywaniu zamian w inny sposób - staramy się w każdej iteracji przesunąć wszystkie duże elementy na sam koniec. Można to porównać do czesania z grzebieniem. Początkowo rozczesujemy włosy grzebieniem z dużym odstępem pomiędzy ząbkami - w ten sposób będzie łatwiej i szybciej rozczesać pojedyncze grupki.

Algorytm sortowania Grzebieniowego zawiera element empiryczny - czyli wyliczony doświadczalnie. Jest to współczynnik w:=1.3. Nie ma on znaczenia dla poprawności posortowania listy, ale ma znaczący wpływ na szybkość wykonywania algorytmu. W ten sposób zwykłe sortowanie bąbelkowe poprawiamy prawdopodobnie do złożoności . Niemniej jest on prawdopodobnie wolniejszy od sortowania szybkiego.

Podczas korzystania z tej metody sortowania korzystamy z wyliczanej w każdej iteracji rozpiętości. Rozpiętość to początkowo długość listy. Na początku iteracji dzielimy aktualną wartość rozpiętości przez współczynnik w=1.3. Część ułamkową po wyliczeniach odrzucamy. Rozpiętość ma kluczowe znaczenie dla ilości wykonywanych porównań w każdej iteracji. Mianowicie porównujemy tylko pary elementów, które są odległe o rozpiętość. Jeśli spełniają kryteria to je zamieniamy tak jak w przypadku sortowania bąbelkowego. Niestety algorytm ten nie wie w ten sposób, kiedy skończyć, dlatego potrzebujemy dodatkowej zmiennej w każdej iteracji, która sprawdzi czy wykonaliśmy jakąkolwiek zamianę, kiedy rozpiętość wynosi 1.

Przykład

Weźmy teraz listę L:={5, 3, 4, 1, 2}. Prześledzimy teraz działanie algorytmu. Przechodzimy do pierwszej iteracji - rozpiętość dla niej to . Po odrzuceniu części ułamkowej rozpiętość wynosi 3. Przechodzimy do porównania par o odległości równej 3:

(Pogrubione zostały elementy porównywane, a kursywą zamienione)

ListaPorównanieNowa lista
5, 3, 4, 1, 25 > 1, zamiana 5 z 11, 3, 4, 5, 2
1, 3, 4, 5, 23 > 2, zamiana 3 z 21, 2, 4, 5, 3

Rozpiętość > 1 i dokonaliśmy zamiany, więc przechodzimy do drugiej iteracji. Na początek wyliczamy rozpiętość: . Na podstawie obliczeń przyjmujemy rozpiętość 2.

ListaPorównanieNowa lista
1, 2, 4, 5, 31 < 4, nie zamieniamy1, 2, 4, 5, 3
1, 2, 4, 5, 32 < 5, nie zamieniamy1, 2, 4, 5, 3
1, 2, 4, 5, 34 > 3, zamieniamy 4 z 31, 2, 3, 5, 4

Przechodzimy do kolejnej iteracji: wyliczamy rozpiętość: czyli rozpiętość wynosi 1. W tym momencie rozpoczynamy sortowanie bąbelkowe. Różnica tkwi w tym, że za każdym razem przeglądamy wszystkie elementy.

ListaPorównanieNowa lista
1, 2, 3, 5, 41 < 2, nie zamieniamy1, 2, 3, 5, 4
1, 2, 3, 5, 42 < 3, nie zamieniamy1, 2, 3, 5, 4
1, 2, 3, 5, 43 < 5, nie zamieniamy1, 2, 3, 5, 4
1, 2, 3, 5, 45 > 4, zamieniamy 5 z 41, 2, 3, 4, 5

Nasza lista jest już posortowana. Jednak program wykonałby jeszcze jedną pętlę, aby się upewnić. Dla takiej listy zmienna sprawdzająca, ile zamian zostało wykonanych, nie zgłosi żadnej. Podsumowując, mamy posortowaną listę L:={1, 2, 3, 4, 5}.

Implementacja

Sortowanie rozpoczynamy od zadeklarowania zmiennych. Sortowanie będzie odbywać się w miejscu, więc nie będziemy zwracać żadnej tablicy. Zmodyfikujemy podaną, jako argument, listę liczb rzeczywistych:

  1. void sort(double* lista, int n) {
  2.   double space = n, temp = 0;
  3.   bool next_i = true;

(1.) Przyjmujemy dwa argumenty: lista - lista do posortowania oraz n - długość listy sortowanej. (2.) Przyjmujemy, że space - to rozpiętość, a temp - przyda nam się do zamieniania elementów miejscami. (3.) Ostatnia zadeklarowana zmienna, to next_i. Jest to wspomniana zmienna, która będzie wykrywać czy w danej iteracji zostały zamienione miejscami jakieś dwa elementy. Jeśli tak to by świadczyło, że jest potrzebna dodatkowa iteracja, która sprawdzi czy lista została posortowana prawidłowo.

  1.   while (space > 1 || next_i){
  2.     space = space / 1.3;
  3.     if(space==0)
  4.       space=1;

(4.) Rozpoczynamy główną pętle while. Wykonujemy ją dopóki rozpiętość space będzie różna od 1 oraz wykonano conajmniej jedną operację zamiany w poprzedniej iteracji. (5.) Wyliczamy aktualną rozpiętość dzieląc space przez 1.3. (6.) Jeśli rozpiętość jest równa 0 to zwiększamy do 1, ponieważ inaczej algorytm porównałby element stojący na pozycji i z elementem na pozycji i.

  1.     next_i = false;
  2.     for (int i=0; i + space < n; ++i) {
  3.       if (tab[i + space] < tab[i]) {
  4.         temp = lista[i];
  5.         lista[i] = lista[i + space];
  6.         lista[i + space] = temp;
  7.         next_i = true;
  8.       }
  9.     }
  10.   }
  11. }

(8.) Resetujemy wskaźnik next_i do wartości domyślnej. (9.) Dla każdej pary elementów pomiędzy którymi jest odległość space: (10.) jeśli spełniają kryteria sortowania to (11. - 13.) zamieniamy miejscami i (14.) sygnalizujemy, że potrzebna jest dodatkowa iteracja.

Testowanie funkcji

Program można przetestować przy pomocy poniższej funkcji main(), która posortuje wprowadzoną listę n liczb rzeczywistych.

  1. int main () {
  2.   int n;
  3.   cin >> n;
  4.   double* L = new double[n];
  5.   for(int i = 0; i < n; i++)
  6.     cin >> L[i];
  7.   sort(L, n);
  8.   for(int i = 0; i < n; i++)
  9.     cout << L[i] << " ";
  10.   delete[] L;
  11.   system("pause");
  12.   return 0;
  13. }

Zadania

Zadanie 1

Zmodyfikuj funkcję, aby sortowała liczby całkowite malejąco.

Przykładowo dla listy [5 2 4 4 6] program wypisze na ekran:

  1. 6 5 4 4 2