0Pricing
C Academy · Урок

qsort с компараторами

Обратные вызовы стандартной библиотеки

«qsort с компараторами» — бесплатный урок C Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.

Стандартная функция qsort

Стандартная библиотека предоставляет функцию qsort в заголовочном файле <stdlib.h>. Это универсальная сортировка, работающая с массивом любого типа благодаря функции обратного вызова для сравнения.

#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;
}

Сигнатура qsort

qsort(base, count, size, compare) принимает начало массива, количество элементов, размер элемента и функцию сравнения.

Функция является универсальной, поскольку работает с необработанными байтами и переданной Вами функцией сравнения.

#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;
}

Контракт функции сравнения

Функция сравнения возвращает отрицательное значение, если первый элемент должен находиться перед вторым, ноль — если элементы равны, и положительное значение — если первый элемент должен находиться после второго.

#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;
}

Приведение указателей void

Функция сравнения получает для каждого элемента указатель const void *. Приведите его к правильному типу и разыменуйте, чтобы прочитать значение.

#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;
}

Порядок по убыванию

Измените направление сравнения, чтобы сортировать элементы от наибольшего к наименьшему.

#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;
}

Предотвращение переполнения при вычитании

Возврат значения x - y может привести к переполнению для больших целых чисел. Безопасная идиома (x > y) - (x < y) позволяет этого избежать.

#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;
}

Сортировка строк

В массиве типа char * каждый элемент сам является указателем, поэтому приведите его к типу const char * const * и сравнивайте с помощью 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;
}

Сортировка структур

qsort также обрабатывает массивы структур. В функции сравнения сравнивайте выбранное поле.

#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 использует тот же принцип

bsearch выполняет двоичный поиск в отсортированном массиве, используя функцию сравнения с тем же контрактом, что и 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;
}

Несколько ключей сортировки

Функция сравнения может сначала сравнивать основное поле, а при равенстве — дополнительное.

#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;
}

Зачем нужна универсальная сортировка

Поскольку qsort отделяет алгоритм от сравнения, одна хорошо протестированная функция может сортировать данные любого сравнимого типа.

#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;
}

Быстрая проверка

Проверьте, насколько хорошо Вы понимаете функции сравнения для qsort.

Итоги

Вы научились использовать qsort с функциями сравнения:

  • qsort(base, count, size, compare) универсально сортирует массив любого типа.
  • Функция сравнения принимает два указателя const void * и возвращает отрицательное значение, ноль или положительное значение.
  • Используйте (x > y) - (x < y), чтобы избежать переполнения.
  • Тот же контракт функции сравнения используется в bsearch, при сортировке структур и при сортировке по нескольким ключам.

Часто задаваемые вопросы

Урок «qsort с компараторами» бесплатный?

Да — полный текст урока «qsort с компараторами» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.

Чему я научусь в уроке «qsort с компараторами»?

Обратные вызовы стандартной библиотеки Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C Academy?

Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «qsort с компараторами»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C Academy?

Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Объявление указателей на функции
  2. Передача функций
  3. qsort с компараторами
  4. Таблицы указателей на функции
← Назад к C Academy