Sortowanie grzebieniowe (ang. comb sort)

[algorytm] Opis działania algorytmu sortowania grzebieniowego wraz z kodem źródłowym.

Złożoność czasowa: O(n*log(n))

Oparte jest na sortowaniu bąbelkowym. Za rozpiętość (gap) przymuje się wielkość tablicy, którą dzięli się przez 1.3 i odrzuca część ułamkową. Następnie bada się kolejno wszystkie pary obiektów odległych o rozpiętość. Gdy rozpiętość osiągnie wartość 1 sortowanie zostanie zakończone.
Do sprawdzenia czy zaszła zmiana podczas sortowania, można użyć dodatkowej zmiennej typu bool, jak w przypadku sortowania bąbelkowego. Przerywane jest wykonywanie algorytmu, gdy podczas przejścia przez całą tablicę nie nastąpiła żadna zamiana.

void Sortowanie( int tab[], int size )
{
int gap = size;
bool replace = true;

while( gap > 1 || replace )
{
gap = gap * 10 / 13;
if( gap == 0 )
gap = 1;

replace = false;
for( int i = 0; i + gap < size; i++ )
{
if( tab[ i + gap ] < tab[ i ] )
{
swap( tab[ i ], tab[ i + gap ] );
replace = true;
}
}
}
}

Więcej informacji: http://pl.wikipedia.org/wiki/Sortowanie_grzebieniowe

Wszystkie teksty są chronione prawami autorskimi. Kopiowanie lub rozpowszechnianie treści poza niniejszym serwisem jest zabronione.

Powyższe ograniczenie nie dotyczy autora opracowania, któremu przysługuje prawo do rozpowszechniania własnego tekstu wedle własnego uznania.