Sortowanie szybkie (ang. quick sort)

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

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

Na początku wybiera się tzw. element osiowy (pewien element tablicy np. jej środek), po czym na początek tablicy przenoszone są wszystkie elementy mniejsze od niego, na koniec większe, a w powstałe między tymi obszarami puste miejsca trafia wybrany element. Następnie sortuje się osobno początkową i końcową część tablicy.

void Sortowanie( int tab[], int left, int right )
{
int i = left;
int j = right;
int x = tab[( left + right ) / 2 ];
do
{
while( tab[ i ] < x )
i++;

while( tab[ j ] > x )
j--;

if( i <= j )
{
swap( tab[ i ], tab[ j ] );

i++;
j--;
}
} while( i <= j );

if( left < j ) Sortowanie( tab, left, j );

if( right > i ) Sortowanie( tab, i, right );

}

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

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.