Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Autor: SeaMonster131
Biblioteki C++

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.

C/C++
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