qsort

[funkcja] Wykonuje algorytm szybkiego sortowania (ang. quicksort).

Składnia

#include <cstdlib>

void qsort(
void * base,
size_t num,
size_t width,
int( * compare )( const void *, const void * )
);

Opis szczegółowy

Funkcja wykonuje algorytm szybkiego sortowania (ang. quicksort) na tablicy przekazanej jako argumet base. Liczbę elementów w tablicy określa argument num, natomiast jako argument width podaje się liczbę bajtów zajmowanych przez jeden element tablicy.

Argumenty

Argument	Opis
const void *base	Wskaźnik na tablicę, która ma zostać posortowana.
size_t num	Liczba elementów w tablicy.
size_t width	Liczba bajtów zajmowanych przez jeden element tablicy.
int (compare ) ( const void , const void *)	Funkcja porównująca elementy tablicy. Do argumentów przedmiotowej funkcji trafiają wskaźniki na elementy obecnie porównywane.

Zwracana wartość

Funkcja qsort nie zwraca żadnej wartości.

Funkcja compare

Funkcja przekazana jako argument compare powinna zwracać następujące wartości:

mniejsze od 0 - gdy wartość argumentu pierwszego jest mniejsza od argumentu drugiego;
równe 0 - gdy wartość argumentu pierwszego jest równa wartości argumentu drugiego;
większe od 0 - gdy wartość argumentu pierwszego jest większa od argumentu drugiego.

Stosując się do powyższych reguł uzyskasz tablicę uporządkowaną rosnąco. Jeżeli chcesz aby tablica była uporządkowana malejąco, musisz odwrócić sens znaczenia sformułowań 'jest mniejsza' oraz 'jest większa' w powyższych regułach.

Przykład

#include <cstdio>
#include <cstdlib>
#include <ctime>

typedef int ElementT;

int sortujRosnaco( const ElementT * arg1, const ElementT * arg2 );
int sortujMalejaco( const ElementT * arg1, const ElementT * arg2 );
void posortuj( ElementT * tablica, int ilosc, int( * funkcjaSortujaca )( const ElementT *, const ElementT * ) );
void wyswietl( ElementT * tablica, int ilosc );

int main()
{
srand( time( 0 ) );
ElementT tablica[ 20 ];
for( int i = sizeof( tablica ) / sizeof( ElementT ) - 1; i >= 0; i-- )
   tablica[ i ] = rand() % 9 + 1;

wyswietl( tablica, sizeof( tablica ) / sizeof( ElementT ) );
posortuj( tablica, sizeof( tablica ) / sizeof( ElementT ), sortujRosnaco );
wyswietl( tablica, sizeof( tablica ) / sizeof( ElementT ) );
posortuj( tablica, sizeof( tablica ) / sizeof( ElementT ), sortujMalejaco );
wyswietl( tablica, sizeof( tablica ) / sizeof( ElementT ) );
return 0;
}

int sortujRosnaco( const ElementT * arg1, const ElementT * arg2 )
{
if( * arg1 <* arg2 )
   return - 1;

if( * arg1 >* arg2 )
   return 1;

return 0;
}

int sortujMalejaco( const ElementT * arg1, const ElementT * arg2 )
{
if( * arg1 >* arg2 )
   return - 1;

if( * arg1 <* arg2 )
   return 1;

return 0;
}

void posortuj( ElementT * tablica, int ilosc, int( * funkcjaSortujaca )( const ElementT *, const ElementT * ) )
{
qsort( tablica, ilosc, sizeof( * tablica ),( int( * )( const void *, const void * ) ) funkcjaSortujaca );
}

void wyswietl( ElementT * tablica, int ilosc )
{
for( int i = 0; i < ilosc; i++ )
   printf( "%d, ", tablica[ i ] );

printf( "\n" );
}

Przykładowy efekt działania programu:

7, 3, 8, 1, 4, 5, 4, 8, 4, 2, 2, 2, 2, 8, 7, 5, 1, 2, 9, 8,
1, 1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 5, 5, 7, 7, 8, 8, 8, 8, 9,
9, 8, 8, 8, 8, 7, 7, 5, 5, 4, 4, 4, 3, 2, 2, 2, 2, 2, 1, 1,

Zagadnienia powiązane

sort	Sortuje elementy w podanym zakresie. (szablon funkcji)

Linki zewnętrzne

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.