qsort z komparatorami
Callbacki biblioteki standardowej
qsort z komparatorami to bezpłatna lekcja C Academy na CoddyKit. To lekcja 3 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.
Standardowa funkcja qsort
Biblioteka standardowa udostępnia funkcję qsort w pliku <stdlib.h>. Jest to uniwersalny algorytm sortowania dowolnego typu tablicy, wykorzystujący funkcję zwrotną porównującą.
#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);
}
int main(void) {
int a[] = {3, 1, 2};
qsort(a, 3, sizeof(int), cmp_int);
printf("%d %d %d\n", a[0], a[1], a[2]);
return 0;
}Sygnatura qsort
qsort(base, count, size, compare) przyjmuje początek tablicy, liczbę elementów, rozmiar elementu oraz funkcję porównującą.
Jest uniwersalna, ponieważ działa na surowych bajtach oraz dostarczonej przez użytkownika funkcji porównującej.
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return *(const int*)a - *(const int*)b;
}
int main(void) {
int a[] = {9, 4, 7, 1};
qsort(a, 4, sizeof(int), cmp);
for (int i = 0; i < 4; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Umowa funkcji porównującej
Funkcja porównująca zwraca wartość ujemną, jeśli pierwszy element powinien znaleźć się przed drugim, zero, jeśli są równe, oraz wartość dodatnią, jeśli powinien znaleźć się za drugim.
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
int x = *(const int*)a, y = *(const int*)b;
if (x < y) return -1;
if (x > y) return 1;
return 0;
}
int main(void) {
int a[] = {5, 2, 8, 2};
qsort(a, 4, sizeof(int), cmp);
for (int i = 0; i < 4; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Rzutowanie wskaźników void
Funkcja porównująca otrzymuje dla każdego elementu wartość typu const void *. Należy rzutować je na właściwy typ i wyłuskać, aby odczytać wartości.
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
double x = *(const double*)a;
double y = *(const double*)b;
return (x > y) - (x < y);
}
int main(void) {
double d[] = {2.5, 1.1, 3.3};
qsort(d, 3, sizeof(double), cmp);
printf("%.1f %.1f %.1f\n", d[0], d[1], d[2]);
return 0;
}Porządek malejący
Odwróć porównanie, aby sortować od największej wartości do najmniejszej.
#include <stdio.h>
#include <stdlib.h>
int 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[] = {1, 5, 3, 2};
qsort(a, 4, sizeof(int), desc);
for (int i = 0; i < 4; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Unikanie przepełnienia przy odejmowaniu
Zwracanie wartości x - y może spowodować przepełnienie dla dużych liczb całkowitych. Bezpieczny idiom (x > y) - (x < y) pozwala tego uniknąć.
#include <stdio.h>
#include <stdlib.h>
int safe_cmp(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[] = {100, -100, 0};
qsort(a, 3, sizeof(int), safe_cmp);
for (int i = 0; i < 3; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Sortowanie napisów
W tablicy typu char * każdy element jest sam w sobie wskaźnikiem, dlatego należy rzutować go na const char * const * i porównywać za pomocą strcmp.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp_str(const void *a, const void *b) {
const char *sa = *(const char * const *)a;
const char *sb = *(const char * const *)b;
return strcmp(sa, sb);
}
int main(void) {
const char *w[] = {"pear", "apple", "fig"};
qsort(w, 3, sizeof(char*), cmp_str);
for (int i = 0; i < 3; i++) printf("%s ", w[i]);
printf("\n");
return 0;
}Sortowanie struktur
qsort obsługuje również tablice struktur. W funkcji porównującej należy porównać wybrane pole.
#include <stdio.h>
#include <stdlib.h>
typedef struct { char name; int age; } Person;
int by_age(const void *a, const void *b) {
int x = ((const Person*)a)->age;
int y = ((const Person*)b)->age;
return (x > y) - (x < y);
}
int main(void) {
Person p[] = {{'C',30},{'A',20},{'B',25}};
qsort(p, 3, sizeof(Person), by_age);
for (int i = 0; i < 3; i++) printf("%c:%d ", p[i].name, p[i].age);
printf("\n");
return 0;
}bsearch korzysta z tej samej zasady
bsearch wykonuje wyszukiwanie binarne w posortowanej tablicy, używając funkcji porównującej z taką samą umową jak qsort.
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(const int*)a) - (*(const int*)b);
}
int main(void) {
int a[] = {1, 3, 5, 7, 9};
int key = 7;
int *found = bsearch(&key, a, 5, sizeof(int), cmp);
printf("found: %d\n", found ? *found : -1);
return 0;
}Wiele kluczy sortowania
Funkcja porównująca może najpierw porównywać pole główne, a następnie pole dodatkowe, gdy wartości pierwszego są równe.
#include <stdio.h>
#include <stdlib.h>
typedef struct { int grade; int id; } Rec;
int cmp(const void *a, const void *b) {
const Rec *x = a, *y = b;
if (x->grade != y->grade) return x->grade - y->grade;
return x->id - y->id;
}
int main(void) {
Rec r[] = {{90,2},{90,1},{80,3}};
qsort(r, 3, sizeof(Rec), cmp);
for (int i = 0; i < 3; i++) printf("%d/%d ", r[i].grade, r[i].id);
printf("\n");
return 0;
}Znaczenie uniwersalnego sortowania
Ponieważ qsort oddziela algorytm od porównywania, jedna dobrze przetestowana funkcja może sortować dowolny porównywalny typ danych.
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
char x = *(const char*)a, y = *(const char*)b;
return (x > y) - (x < y);
}
int main(void) {
char s[] = "dcba";
qsort(s, 4, sizeof(char), cmp);
printf("%s\n", s);
return 0;
}Szybki sprawdzian
Sprawdź swoją wiedzę o funkcjach porównujących używanych przez qsort.
Podsumowanie
Dowiedział się Pan / Dowiedziała się Pani, jak używać qsort z funkcjami porównującymi:
qsort(base, count, size, compare)sortuje dowolną tablicę w sposób uniwersalny.- Funkcja porównująca przyjmuje dwa argumenty typu
const void *i zwraca wartość ujemną, zero lub dodatnią. - Używaj
(x > y) - (x < y), aby uniknąć przepełnienia. - Ta sama umowa funkcji porównującej jest używana przez
bsearch, sortowanie struktur i sortowanie według wielu kluczy.
Często zadawane pytania
Czy lekcja „qsort z komparatorami” jest bezpłatna?
Tak — pełny tekst „qsort z komparatorami” 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 „qsort z komparatorami”?
Callbacki 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 3 z 4.
Ile czasu zajmuje lekcja „qsort z komparatorami”?
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.
Wszystkie lekcje w tym kursie
- Deklarowanie wskaźników do funkcji
- Przekazywanie funkcji
- qsort z komparatorami
- Tabele wskaźników do funkcji