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;
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;
return gap;
}
