Sortowanie grzebieniowe

Sortowanie grzebieniowe

Przykładowe działanie algorytmu
Rodzaj	sortowanie
Struktura danych	tablica

Sortowanie grzebieniowe (ang. combsort) – wynaleziona w 1980 przez Włodzimierza Dobosiewicza^[1], odkryta ponownie i opisana w 1991 roku przez Stephena Laceya 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ść przyjmuje się długość tablicy, dzieli się rozpiętość przez 1.3, odrzuca część ułamkową
• bada się kolejno wszystkie pary obiektów odległych o rozpiętość (jeśli są ułożone niemonotonicznie - zamienia się je miejscami)
• wykonuje się 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żna określić, czy dane są już posortowane czy nie. W tym celu można użyć zmiennej typu bool, która jest ustawiana po zamianie elementów tablicy miejscami. Przerywane jest wykonywanie algorytmu, gdy podczas przejścia przez całą tablicę nie nastąpiła zamiana.

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

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 dzielona jest 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 i 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;
}

Przykład w języku pascal

procedure Combsort(var a : array of Integer; n:Integer);
   
    function newGap(gap : Integer):integer;
    begin
        gap := trunc(gap / 1.3); //wymagany moduł "math"
        if (gap = 9) OR (gap=10) then
            gap := 11; //warunek tylko dla Combsort 11
        if gap < 1 then
            gap := 1;
        newGap:=gap;
    end;
    
var
    gap, i, j : Integer;
    x : Integer; 
    swapped : Boolean;
begin
    gap := n;
    repeat
        gap := newGap(gap);
        swapped := false;
        for i := 0 to n-gap-1 do
        begin
            j := i + gap;
            if a[i] > a[j] then
            begin
                x := a[i];
                a[i] := a[j];
                a[j] := x;
                swapped := true;
            end;
        end;
    until (gap = 1) and (not swapped);
end;

Przypisy