|
Sortowanie grzebieniowe
Sortowanie grzebienioweSortowanie grzebieniowe (
ang.
combsort) – wynaleziona w 1980 przez Włodzimierza Dobosiewicza, odkryta ponownie i opisana 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ść 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:tab; n:integer); function newGap(gap:integer):integer; begin gap := trunc(gap / 1.3); if (gap = 9) OR (gap=10) then gap := 11; if gap < 1 then gap := 1; newGap:=gap; end;var top, gap, i, j : integer; x : element; swapped : boolean;begin gap := n; repeat gap := newGap(gap); top := n - gap; swapped := false; for i := 1 to top 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; Bibliografia- Wlodzimierz Dobosiewicz. An Efficient Variation of Bubble Sort. „Inf. Process. Lett.”. 11(1): 5-6 (1980).
Inne hasła zawierające informacje o "Sortowanie grzebieniowe":
Sortowanie
– może być stabilne po odpowiednich zmianach
sortowanie Shella
– (ang. shellsort) złożoność nieznana;
Sortowanie grzebieniowe
– (ang. combsort) złożoność nieznana;
sortowanie szybkie
– (ang. quicksort) Θ(nlogn), ...
Kod pocztowy
...
Sortowanie bąbelkowe
...
Sortowanie przez scalanie
...
Sortowanie przez zliczanie
...
Sortowanie kubełkowe
...
Sortowanie pozycyjne
...
Sortowanie biblioteczne
...
Sortowanie przez wybieranie
...
Sortowanie Shella
...
Inne lekcje zawierające informacje o "Sortowanie grzebieniowe":
Zagrożenia gleb (plansza 21)
...
Algorytmy sortujące - sortowanie przez wstawianie, sortowanie przez wybór (plansza 3)
...
Algorytmy sortujące - sortowanie bąbelkowe, część II (plansza 10)
...
|
|
|
|