Sortowanie grzebieniowe

Z Wikipedii

Sortowanie grzebieniowe (ang. combsort) – opublikowana w 1991 roku przez Stephena Lacey'a i Richarda Boxa metoda sortowania tablicowego. Jej główne cechy to:

• oparta na metodzie bubblesort (sortowanie bąbelkowe)
• prawdopodobnie złożoność wynosi O(n log n), statystycznie gorsza niż quicksort (sortowanie szybkie)
• włączono empirię - współczynnik 1.3 wyznaczony doświadczalnie

wariant podstawowy:

• za rozpiętość przyjmij długość tablicy, podziel rozpiętość przez 1.3, odrzuć część ułamkową
• badaj kolejno wszystkie pary obiektów odległych o rozpiętość (jeśli są ułożone niemonotonicznie - zamień miejscami)
  
• wykonuj powyższe w pętli dzieląc rozpiętość przez 1.3 do czasu, gdy rozpiętość osiągnie wartość 1.

Gdy rozpiętość spadnie do 1 metoda zachowuje się tak jak sortowanie bąbelkowe. Tylko wtedy możemy określić, czy dane są już posortowane czy nie. W tym celu możemy użyć zmiennej typu bool, która jest ustawiana po zamianie elementów tablicy miejscami. Przerywamy wykonywanie algorytmu, gdy podczas przejścia przez całą tablicę nie nastąpiła zamiana.

Wariant Combsort 11: rozpiętość 9 i 10 zastępujemy 11

[edytuj] Przykład w języku C / C++

• tab - tablica elementów (w przykładzie tablica liczb całkowitych)
• gap - rozpiętość; w kolejnych iteracjach pętli dzielimy przez współczynnik 1.3
• tmp - zmienna całkowitoliczbowa; do zamiany elementów
• swapped - zmienna logiczna; czy dokonano zamiany elementów

void combSort(int* tab, int size)
{
   int gap = size, tmp;
   bool swapped = true;
   while (gap > 1 || swapped){ // jeśli gap = 1 lub nie dokonano zamiany - wyjście z pętli     
      gap = gap * 10 / 13;
      if(gap==0)
            gap=1;
      swapped = false;
      for ( int i = 0; i + gap < size; ++i ) { // wykonuj od 0 do ostatniego elementu tablicy
         if ( tab[i + gap] < tab[i] ) {   // porównanie elementów odległych o rozpiętość
            tmp = tab[i];                 // zamiana elementów
            tab[i] = tab[i + gap];
            tab[i + gap] = tmp;
            swapped = true;
           }
      }
   }
}

Funkcja do wyznaczania współczynnika rozpiętości (Wariant Combsort 11)

int newGap(int gap)
{
   gap = gap * 10 / 13;
   if ( gap == 9 || gap == 10 ) gap = 11;
   if(gap==0) gap=1;
   return gap;
}