Sortowanie koktajlowe (ang. shake sort)

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

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

Sortowanie koktajlowe jest odmianą sortowania bąbelkowego, które sortuje elementy w zbiorze w dwóch kierunkach. Różni się od niego tym, że zamiast wielokrotnie przechodzić przez listę od dołu do góry przechodzi na przemian z dołu do góry i następnie z góry do dołu. Dzięki temu sortowanie koktajlowe ma trochę lepsze osiągi niż standardowe sortowanie bąbelkowe.

void Sortowanie( int tab[], int size )
{
int bottom = 0, top = size - 1;
bool replace = true;

while( replace )
{
replace = false;

for( int i = bottom; i < top; i++ )
{
if( tab[ i ] > tab[ i + 1 ] )
{
swap( tab[ i ], tab[ i + 1 ] );

replace = true;
}
}

top--;
for( int i = top; i > bottom; i-- )
{
if( tab[ i ] < tab[ i - 1 ] )
{
swap( tab[ i ], tab[ i - 1 ] );

replace = true;
}
}

bottom++;
}
}

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

Dodatkowe informacje

Algorytm sortowania koktajlowego znany jest również pod nazwami:

dwukierunkowe sortowanie bąbelkowe
sortowanie przez wstrząsanie

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.