Прежде чем переходить к реализации алгоритмов сортировка, необходимо ответить себе на ряд вопросов, для более точного понимания требований к алгоритму:

1. Нужно ли сортировать по возрастанию ($S_i \le S_{i+1}$) или по убыванию ($S_i \ge S_{i+1}$),
2. В задачах зачастую сортируются не просто числа, а сложные структуры. Необходимо понимать, какое поле является ключом сортировки. Разумеется при этом всём необходимо сохранить целостность записи.
3. Что делать, если у двух записей одинаковый ключ, в каком порядке тогда они должны идти?

Говоря отдельно про пункт 3 - для решения подобной проблемы зачастую используется второй ключ (Пример: в структуре хранящей ФИО и номер телефона, первым ключом будет являться ФИО, а вторым номер - телефона). Иногда важно сохранять исходным порядок элементов с одинаковыми ключами, алгоритмы способные на это называются stable.

Некоторые алгоритмы сортировки, если не предусмотреть этот момент и в данных будет много одинаковых ключей, могут деградировать до скорости O(n^2).

4. Что делать, если поступают нечисловые данные? Сортировка строк сложнее, чем числе. Необходимо учитывать регистр, алфавитный порядок, знаки препинания.

Правильным решением всех этих тонкостей будет использование функции попарного сравнения элементов (компаратор), каждая из которых будет заточена под конкретную задачу. Эта функция принимает на вход два указателя на элементы a и b и возвращает -1, если a < b, 1, если a > b, и 0, если a = b.

Такой подход позволяет не обращать внимания на детали и применять общие алгоритмы сортировки к любым данным. Мы просто передаём функцию сравнения процедуре сортировки в качестве аргумента. Обычно использование этой функции предпочтительнее написания своей собственной процедуры сортировки.

#include <stdlib.h>
void qsort(void *base, size_t nel, size_t width, 
           int (*compare)(const void *, const void *));

При использовании функции qsort, важно понимать значение её аргументов:

• Аргумент base - указатель на массив.
• Функция сортирует первые nel элементов массива.
• Длинна элементов составляет width байтов

Порядок отсортированной последовательности определяется функцией compare. Она принимает в качестве аргументов указатели на два элемента размером width и возвращает отрицательное число, если в отсортированной последовательности первый элемент должен быть перед вторым, положительное число, если наоборот, и ноль, если элементы одинаковы.

Пример функции для сравнения целых чисел в возрастающей последовательности приведён в листинге 4.1.

int intcompare(int *i, int *j)
{
    if (*i > *j) return (1);
    if (*i < *j) return (-1);
    return (0);
}

Функцию сортировки qsort можно использовать при сортировке массива a, в котором заняты первые n ячеек. Функция вызывается данным кодом:

qsort(a, n, sizeof(int), intcompare);

Название функции сортировки qsort намекает, что в ней реализован алгоритм быстрой сортировки (quicksort), но для пользователя это обычно не имеет значения — главное, что функция работает.

1. Стивен Скиена - "Алгоритмы. Руководство по раразобке" - 2022 (стр. 143-145)
2. Роджер Пенроуз - "Новый ум короля" - 2008