Как отсортировать массив в C

Справочник · C · 1 минута чтения

В C есть готовая сортировка — функция 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[] = {5, -3, 12, 0, 7, 7, 1};
    int n = sizeof(a) / sizeof(a[0]);
    qsort(a, n, sizeof(a[0]), cmp_int);
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

Вывод

-3 0 1 5 7 7 12

Аргументы qsort: массив, число элементов, размер одного элемента и функция сравнения.

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

qsort сортирует что угодно, поэтому передаёт в функцию сравнения адреса элементов как const void * — «адрес чего-то». Внутри адрес приводят к нужному типу (const int *) и берут значение *. Функция должна вернуть:

отрицательное число — если a должен идти раньше b;
0 — если элементы равны;
положительное число — если a должен идти позже.

Запись (x > y) - (x < y) даёт ровно −1, 0 или 1. Часто пишут короче — return x - y;, но для больших чисел разность переполняет int (например, 2 000 000 000 − (−2 000 000 000)), и сортировка становится неверной.

По убыванию — поменяйте местами x и y: return (y > x) - (y < x);.

Массив строк

Элементы такого массива — указатели char *, поэтому в функцию сравнения приходят адреса указателей:

#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 *words[] = {"pear", "apple", "kiwi", "banana"};
    int n = sizeof(words) / sizeof(words[0]);
    qsort(words, n, sizeof(words[0]), cmp_str);
    for (int i = 0; i < n; i++) {
        printf("%s\n", words[i]);
    }
    return 0;
}

Вывод

apple
banana
kiwi
pear

Массив структур по полю

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    char name[20];
    int score;
} Player;

int by_score_desc(const void *a, const void *b) {
    const Player *p = a;
    const Player *q = b;
    return (q->score > p->score) - (q->score < p->score);
}

int main(void) {
    Player t[] = {{"Ann", 70}, {"Bob", 95}, {"Kate", 82}};
    qsort(t, 3, sizeof(t[0]), by_score_desc);
    for (int i = 0; i < 3; i++) {
        printf("%s %d\n", t[i].name, t[i].score);
    }
    return 0;
}

Вывод

Bob 95
Kate 82
Ann 70

qsort не обещает сохранить порядок равных элементов. Если при равных баллах важен порядок, добавьте в функцию сравнения второе условие, например по имени через strcmp.

Сортировка пузырьком

В школьных задачах часто просят написать сортировку самому. Самая простая — пузырьком: соседние элементы, стоящие не по порядку, меняются местами, и так проход за проходом.

#include <stdio.h>

int main(void) {
    int a[] = {4, 1, 3, 9, 2};
    int n = 5;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

Вывод

1 2 3 4 9

После каждого прохода самый большой из оставшихся элементов «всплывает» в конец, поэтому внутренний цикл с каждым разом короче (n - 1 - i). Пузырёк делает порядка n² сравнений: для тысячи чисел это мгновенно, а для миллиона — слишком долго. Для больших массивов берите qsort.