0Pricing
C Academy · Урок

Использование qsort

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

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

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

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

Сигнатура qsort

Прототип имеет следующий вид:

  • base — указатель на первый элемент
  • nmemb — количество элементов
  • size — размер одного элемента в байтах
  • compar — указатель на функцию сравнения

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

Написание функции сравнения

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

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

Не вычитайте значения в функциях сравнения

Возврат значения x - y может привести к переполнению для больших целых чисел и дать неверный результат. Вместо этого используйте идиому разности логических значений (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;
}

Сортировка по убыванию

Чтобы сортировать по убыванию, просто измените знак результата сравнения.

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

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

Чтобы отсортировать массив 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 *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;
}

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

Массив структур можно сортировать по любому полю. Здесь мы упорядочиваем людей по возрасту.

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

Сортировка по нескольким ключам

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

#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 не является стабильной

Стандарт C не требует, чтобы qsort была стабильной. Если Вам нужна стабильность, добавьте в функцию сравнения ключ для разрешения равенства, например исходный индекс.

Дополнение к bsearch

bsearch выполняет двоичный поиск в отсортированном массиве, используя такой же стиль функции сравнения. Используйте её вместе с qsort для быстрого поиска.

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

Зачем использовать qsort

Стандартная qsort хорошо протестирована, часто представляет собой настроенный гибрид с интроспективной сортировкой и работает с любым типом. Используйте собственную сортировку только тогда, когда Вам нужна стабильность или особое поведение, которое библиотека не может обеспечить.

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

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

Итоги

Вы научились использовать сортировку из стандартной библиотеки.

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

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

Урок «Использование qsort» бесплатный?

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

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

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

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

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

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

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

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

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

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

  1. Сортировка пузырьком и вставками
  2. Быстрая сортировка
  3. Сортировка слиянием
  4. Использование qsort
← Назад к C Academy