Używanie qsort
Sortowanie z biblioteki standardowej
Używanie qsort to bezpłatna lekcja C Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.
Sortowanie w bibliotece standardowej
Biblioteka standardowa języka C udostępnia funkcję qsort w <stdlib.h>. Sortuje ona dowolną tablicę za pomocą funkcji porównującej, dlatego rzadko trzeba pisać własny algorytm sortowania.
Sygnatura qsort
Prototyp wygląda następująco:
basewskaźnik do pierwszego elementunmembliczba elementówsizeliczba bajtów przypadających na elementcomparwskaźnik do funkcji porównującej
void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
Pisanie funkcji porównującej
Funkcja porównująca otrzymuje dwa argumenty typu const void *. Należy rzutować je na właściwy typ, wyłuskać wartości i zwrócić liczbę ujemną, zero albo liczbę dodatnią.
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void *a, const void *b) {
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y); /* safe, no overflow */
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
qsort(a, 5, sizeof(int), cmp_int);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Unikanie odejmowania w funkcjach porównujących
Zwracanie wartości x - y może spowodować przepełnienie dla dużych liczb całkowitych, prowadząc do błędnych wyników. Zamiast tego należy użyć idiomu różnicy wartości logicznych (x > y) - (x < y).
#include <stdio.h>
int main(void) {
int x = 2000000000, y = -2000000000;
printf("unsafe x-y = %d\n", x - y); /* overflow */
printf("safe = %d\n", (x > y) - (x < y));
return 0;
}Kolejność malejąca
Aby sortować malejąco, wystarczy odwrócić wynik porównania.
#include <stdio.h>
#include <stdlib.h>
int cmp_desc(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (y > x) - (y < x);
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
qsort(a, 5, sizeof(int), cmp_desc);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Sortowanie ciągów znaków
Aby posortować tablicę elementów char *, funkcja porównująca otrzymuje wskaźniki do tych wskaźników. Należy rzutować je na const char * const * i wywołać strcmp.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp_str(const void *a, const void *b) {
const char *x = *(const char * const *)a;
const char *y = *(const char * const *)b;
return strcmp(x, y);
}
int main(void) {
const char *names[] = {"charlie", "alice", "bob"};
qsort(names, 3, sizeof(char *), cmp_str);
for (int i = 0; i < 3; i++) printf("%s ", names[i]);
printf("\n");
return 0;
}Sortowanie struktur
Tablicę struktur można sortować według dowolnego pola. W tym przykładzie osoby porządkujemy według wieku.
#include <stdio.h>
#include <stdlib.h>
typedef struct { char name[16]; int age; } Person;
int by_age(const void *a, const void *b) {
const Person *p = a, *q = b;
return (p->age > q->age) - (p->age < q->age);
}
int main(void) {
Person ppl[] = {{"Ann", 30}, {"Ben", 25}, {"Cid", 40}};
qsort(ppl, 3, sizeof(Person), by_age);
for (int i = 0; i < 3; i++) printf("%s %d\n", ppl[i].name, ppl[i].age);
return 0;
}Sortowanie według wielu kluczy
Aby rozstrzygnąć remis, należy porównać drugie pole, gdy pierwsze jest równe. W ten sposób elementy są sortowane najpierw według wieku, a następnie alfabetycznie według imienia.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct { char name[16]; int age; } Person;
int cmp(const void *a, const void *b) {
const Person *p = a, *q = b;
if (p->age != q->age)
return (p->age > q->age) - (p->age < q->age);
return strcmp(p->name, q->name);
}
int main(void) {
Person ppl[] = {{"Zoe", 30}, {"Amy", 30}, {"Bo", 25}};
qsort(ppl, 3, sizeof(Person), cmp);
for (int i = 0; i < 3; i++) printf("%d %s\n", ppl[i].age, ppl[i].name);
return 0;
}qsort nie jest stabilny
Standard języka C nie wymaga, aby qsort był stabilny. Jeśli potrzebują Państwo stabilności, należy dodać do funkcji porównującej klucz rozstrzygający remis, na przykład pierwotny indeks.
Funkcja bsearch
bsearch wykonuje wyszukiwanie binarne w posortowanej tablicy, używając funkcji porównującej w tym samym stylu. W połączeniu z qsort umożliwia szybkie wyszukiwanie.
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (x > y) - (x < y);
}
int main(void) {
int a[] = {1, 3, 5, 7, 9};
int key = 7;
int *found = bsearch(&key, a, 5, sizeof(int), cmp_int);
printf("%s\n", found ? "found" : "missing");
return 0;
}Dlaczego używać qsort
Standardowa funkcja qsort jest dobrze przetestowana, często stanowi dostrojoną hybrydę introsort i działa z dowolnym typem. Po własny algorytm sortowania warto sięgać tylko wtedy, gdy potrzebna jest stabilność lub specjalne zachowanie, którego biblioteka nie zapewnia.
Szybkie sprawdzenie
Sprawdź swoją wiedzę na temat qsort.
Podsumowanie
Ukończyli Państwo naukę korzystania z sortowania w bibliotece standardowej.
qsort(base, nmemb, size, compar)sortuje dowolną tablicę- Funkcje porównujące rzutują
const void *i zwracają znak wyniku porównania - Należy unikać odejmowania; zamiast tego używać
(x > y) - (x < y) qsortnie gwarantuje stabilności;bsearchjest powiązaną funkcją wyszukiwania
Często zadawane pytania
Czy lekcja „Używanie qsort” jest bezpłatna?
Tak — pełny tekst „Używanie qsort” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Używanie qsort”?
Sortowanie z biblioteki standardowej Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć C Academy?
Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Używanie qsort”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?
Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.