C sort - как быстро отсортировать данные в C++

C++ - один из самых популярных языков программирования в мире. Отсортировать данные в C++ можно несколькими способами. В этой статье мы подробно разберем две функции: стандартную библиотечную qsort() и более современную std::sort. Узнайте, как ими пользоваться, сравните производительность и выберите оптимальный вариант для ваших задач.

Qsort - стандартная сортировка в C

Функция qsort() была добавлена в стандартную библиотеку C еще в далеком 1989 году. Она реализует так называемую "быструю сортировку", хотя на самом деле это необязательно именно алгоритм quicksort. Реализация зависит от компилятора.

Главное преимущество qsort - ее универсальность. С помощью передачи указателя на сравнительную функцию, qsort может отсортировать практически любые данные. Это объясняет ее популярность и долгую "жизнь" в C.

Давайте посмотрим, как вызывается qsort:

qsort(void *array, size_t count, size_t size, int (*compar)(const void *, const void*));

Здесь:

array - указатель на сортируемый массив
count - количество элементов в массиве
size - размер одного элемента в байтах
compar - указатель на сравнительную функцию

Давайте посмотрим, как отсортировать простой массив целых чисел:

int values[] = { 5, 3, 6, 2, 4 }; int compare(const void* a, const void* b) { return ( *(int*)a - *(int*)b ); } qsort(values, 5, sizeof(int), compare);

В сравнительной функции мы приводим указатели к int, разименовываем их и вычитаем. Таким образом числа сортируются по возрастанию. Чтобы отсортировать строки, нам понадобится функция strcmp():

char *names[] = {"John", "Bob", "Alice"}; int compare(const void* a, const void* b) { return strcmp(*(char**)a, *(char**)b); } qsort(names, 3, sizeof(char*), compare);

А для структур данных можно создать специальную сравнительную функцию, которая будет сравнивать нужные поля:

// структура struct Person { char name[100]; int age; }; // массив структур Person people[] = {...}; // сравнение по полю age int compareByAge(const void* a, const void* b) { Person *p1 = (Person *)a; Person *p2 = (Person *)b; return (p1->age - p2->age); } // сортировка qsort(people, 5, sizeof(Person), compareByAge);

Как видно из примеров, qsort довольно проста в использовании. Но у нее есть и недостатки:

Невозможность прервать выполнение посередине
Сложность анализа производительности
Нестабильность порядка одинаковых элементов

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

Сортировка в С++ с помощью std::sort

Функция std::sort появилась в стандартной библиотеке C++ (STL) в 1994 году. В отличие от универсальной qsort, она предназначена специально для работы с контейнерами в C++.

По скорости std::sort на порядок превосходит qsort на эквивалентных данных благодаря более эффективным алгоритмам и оптимизациям компилятора.

Давайте посмотрим на прототипы std::sort:

// для массивов template< class RandomIt > void sort( RandomIt first, RandomIt last ); // для контейнеров template< class Container > void sort( Container& c );

Синтаксис гораздо проще, чем у qsort. Для массива нужно передать только итераторы на начало и конец, а для контейнера - сам контейнер:

std::vector<int> vec = {5, 3, 6, 2, 4}; std::sort(vec.begin(), vec.end()); std::list<Person> people = {...}; std::sort(people);

По умолчанию элементы сортируются по возрастанию. Чтобы изменить порядок, можно передать функцию сравнения:

bool compareDesc(int a, int b) { return a > b; } std::sort(vec.begin(), vec.end(), compareDesc);

Вот основные преимущества std::sort перед qsort:

Более высокая производительность на эквивалентных данных
Простота использования
Стабильность порядка одинаковых элементов
Возможность дополнительных оптимизаций (например, параллельная сортировка)

Но есть и недостаток - std::sort работает только с контейнерами С++, в отличие от универсальной qsort.

Таким образом, при работе с контейнерами в С++ предпочтительно использовать std::sort. А для сортировки произвольных массивов по-прежнему актуальна старая добрая qsort().

c sort

функция sort c

Производительность qsort

Как уже упоминалось, по скорости работы qsort обычно уступает более современным алгоритмам сортировки. Однако с помощью нескольких оптимизаций можно значительно улучшить ее производительность.

Во-первых, очень важно миниминмаксиминмизировать количество сравнений внутри цикла сортировки. Для этого сравнение лучше вынести в отдельную функцию. Таким образом достигается эффект инлайнинга, и сравнения выполняются значительно быстрее.

Во-вторых, если позволяет тип данных, имеет смысл использовать алгоритмы, основанные на целочисленнй арифметике. Например, для типа int вместо вызова strcmp() можно просто вычитать числа.

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

Тщательная оптимизация сравнительной функции и грамотный выбор алгоритма сортировки могут ускорить работу qsort в разы.

Стабильность порядка элементов

Одним из недостатков классической qsort является то, что порядок следования одинаковых элементов после сортировки не гарантируется. Например, если в исходном массиве было [2, 5, 2, 3], то после сортировки может получиться и [2, 2, 3, 5] и [2, 3, 5, 2].

Такая неопределенность часто нежелательна. К счастью, можно модифицировать алгоритм сортировки так, чтобы получить стабильный порядок элементов. Для этого достаточно добавить проверку на равенство элементов внутри цикла сравнения.

if (compar(a, b) > 0) // меняем местами else if (compar(a, b) == 0) // оставляем как есть else // меняем местами

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

Тонкая настройка std::sort

Хотя std::sort и так очень быстра, иногда требуется дополнительная оптимизация производительности. Существует несколько способов это сделать.

Во-первых, можно воспользоваться параллельными версиями std::sort, такими как __gnu_parallel::sort, которые распараллеливают сортировку между несколькими потоками. Это особенно эффективно на многопроцессорных системах.

Во-вторых, для очень больших наборов данных имеет smysl использовать сортировку с предварительной индексацией. Сначала создается вспомогательный индекс, по которому затем происходит сортировка. Это позволяет уменьшить количество сравнений.

В-третьих, можно настроить размер порции (chunk size) при сортировке. Уменьшение размера порции способствует лучшей локализации данных и кэшированию.

Грамотная тонкая настройка параметров std::sort позволяет ускорить ее работу в определенных сценариях.

Выбор между qsort и std::sort

Итак, мы детально рассмотрели две основные функции сортировки в C/C++. Как же выбрать между qsort и std::sort для конкретной задачи?

В целом, при работе исключительно с контейнерами С++ следует отдавать предпочтение std::sort. Она проще в использовании и быстрее работает. А вот для сортировки произвольных массивов по-прежнему удобнее использовать универсальную qsort.

Конечно, возможны и гибридные решения, когда сначала выполняется предварительная сортировка через std::sort, а затем уточняющая сортировка через qsort с пользовательской функцией сравнения. Таким образом можно получить максимальную производительность.

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

Лилия Шевчук 4 ноября, 2023