W bibliotece standardowej znajduje się funkcja qsort, która sortuje tablice. Na początek przestudiujemy jej prototyp, aby zorientować się, w jaki sposób możemy jej używać. Znajduje się on w pliku nagłówkowym stdlib.h
void qsort(void *b, size_t n, size_t s, int(*f)(const void *));
Wygląda to troszkę skomplikowanie, ale musimy nauczyć się odczytywać takie teksty. Funkcja qsort jest typu void, tzn. nie zwraca rezultatu. Lista argumentów przedstawia się następująco:
- void * - W języku programowania C deklarujemy wskaźnik, jako void, kiedy nie wiemy, jaki będzie typ wskazywanego przezeń obiektu. void * określa wskaźnik, który może wskazywać na cokolwiek. A więc funkcja qsort potrzebuje tablicy do posortowania (jej nazwa to wskaźnik do zerowego elementu). Ta tablica może składać się z czegokolwiek (liczb całkowitych, struktur zdefiniowanych przez użytkownika czy liczb zmiennopozycyjnych podwójnej precyzji). To cokolwiek to właśnie void.
- size_t n - Nie jest to znany nam typ, więc musiał być wcześniej zdefiniowany w pliku stdlib.h. Zauważmy, iż na początku pliku stdlib.h znajduje się dyrektywa preprocesora włączająca kolejny plik nagłówkowy o nazwie stddef.h. To właśnie w nim pojawia się definicja typu size_t. Wygląda ona następująco:
typedef unsigned int size_t;
Widzimy tutaj, że zmienna typu size_t jest liczbą całkowitą bez znaku (unsigned int). W naszym przypadku size_t n oznacza liczbę elementów w tablicy.
- size_t s - ten argument zawiera rozmiar każdego elementu tablicy, tzn. wielkość każdego elementu w bajtach. Jeśli przekażemy do funkcji tablicę 56 liczb zmiennopozycyjnych podwójnej precyzji, tym argumentem będzie 8 (wielkość typu double), a poprzedzającym 56 (liczba elementów tablicy).
- int (*f)(const void *) - Ostatnim argumentem jest wskaźnik do funkcji (function pointer), która zwraca wartość całkowitą, a jako argument pobiera wskaźnik do obiektu typu void, który nie może być zmieniony przez ten wskaźnik (specyfikator const). Funkcja ta jest pomocna przy określaniu, czy dany element (n) jest mniejszy, równy bądź większy od następnego (n + 1). Zwraca ona liczbę całkowitą, której wartość zależy od relacji porównania dwóch elementów tablicy; przedstawia to poniższa tabelka:
relacja |
n < n + 1 |
n == n + 1 |
n > n + 1 |
wartość zwracana |
liczba mniejsza od zera |
zero |
liczba większa od zera |
Aby lepiej zrozumieć o co tu chodzi załadujmy program qsort.c, który zlicza ilość wystąpień każdego znaku w podanym pliku. Program sortuje też znaki według częstości występowania.