qсортировка
qsort — это стандартной библиотеки C функция , которая реализует алгоритм сортировки массивов произвольных объектов в соответствии с предоставленной пользователем функцией сравнения. Он назван в честь алгоритма «быстрой сортировки». [1] ( вариант быстрой сортировки, созданный RS Scowen), который изначально использовался для его реализации в библиотеке C Unix , хотя стандарт C не требует реализации быстрой сортировки. [2]
Возможность работать с разными видами данных ( полиморфизм ) достигается за счет использования указателя функции на функцию трехстороннего сравнения , а также параметра, определяющего размер ее отдельных входных объектов. Стандарт C требует, чтобы функция сравнения реализовывала общий порядок элементов входного массива. [3]
История
[ редактировать ]Функция qsort появилась в Unix версии 2 в 1972 году как библиотечная подпрограмма языка ассемблера . Его интерфейс отличается от современной версии тем, что его можно псевдопрототипировать как qsort(void * start, void * end, unsigned length) – сортировка последовательно хранящихся байтовых строк длины -длины из диапазона [ start , end ). [1] Это, а также отсутствие заменяемой функции сравнения, делает невозможным правильную сортировку целых чисел с прямым порядком байтов в системе или любых других структур данных.
В версии 3 Unix интерфейс расширяется за счет вызова compar(III) с интерфейсом, идентичным современному memcmp . Эта функция может быть переопределена программой пользователя для реализации любого вида упорядочивания аналогично функции compar аргумент стандартной qsort (хотя, конечно, глобальный для программы). [4]
Версия 4 Unix добавляет реализацию C с интерфейсом, эквивалентным стандарту. [5] Он был переписан в 1983 году для Berkeley Software Distribution . [2] Функция была стандартизирована в ANSI C (1989). Реализация сборки удалена в версии 6 Unix . [6]
В 1991 году сотрудники Bell Labs заметили, что версии qsort для AT&T и BSD требуют квадратичного времени для некоторых простых входных данных. Таким образом, Джон Бентли и Дуглас Макилрой разработали новую, более быструю и надежную реализацию. [2] Позже, в 1998 году, Макилрой создал более сложную входную информацию в квадратичном времени, названную AntiQuicksort . Эта функция создает данные о противнике «на лету». [7]
Пример
[ редактировать ]Следующий фрагмент кода C показывает, как сортировать список целых чисел с помощью qsort.
#include <stdlib.h>
/* Comparison function. Receives two generic (void) pointers to the items under comparison. */
int compare_ints(const void *p, const void *q) {
int x = *(const int *)p;
int y = *(const int *)q;
/* Avoid return x - y, which can cause undefined behaviour
because of signed integer overflow. */
if (x < y)
return -1; // Return -1 if you want ascending, 1 if you want descending order.
else if (x > y)
return 1; // Return 1 if you want ascending, -1 if you want descending order.
return 0;
// All the logic is often alternatively written:
return (x > y) - (x < y);
}
/* Sort an array of n integers, pointed to by a. */
void sort_ints(int *a, size_t n) {
qsort(a, n, sizeof(*a), compare_ints);
}
Расширения
[ редактировать ]Поскольку функция сравнения оригинала qsort принимает только два указателя, передача дополнительных параметров (например, создание функции сравнения, которая сравнивает разницу двух значений с другим значением) должна выполняться с использованием глобальных переменных . Проблема была решена в BSD и GNU Unix-подобных системах путем введения qsort_r функция, которая позволяет передать дополнительный параметр в функцию сравнения. Две версии qsort_r имеют разные порядки аргументов. C11 Приложение K определяет qsort_s по сути идентичен GNU qsort_r. Библиотеки macOS и FreeBSD также содержат qsort_b, вариант, который использует блоки , аналог замыканий , в качестве альтернативного решения той же проблемы. [8]
Ссылки
[ редактировать ]- ^ Jump up to: а б «Руководство программиста UNIX, второе издание» (PDF) . Телефонные лаборатории Белла . 12 июня 1972 г. с. 193. Архивировано (PDF) из оригинала 30 июля 2023 года . Получено 24 июля 2024 г. - через Общество наследия Unix .
- ^ Jump up to: а б с Бентли, Джон Л.; Макилрой, М. Дуглас (1993). «Разработка функции сортировки» . Программное обеспечение: практика и опыт . 23 (11): 1249–1265. CiteSeerX 10.1.1.14.8162 . дои : 10.1002/сп.4380231105 . S2CID 8822797 . Архивировано из оригинала 16 января 2014 г. Проверено 14 января 2014 г.
- ^ ISO/IEC 9899:201x, Языки программирования — C (проект). §7.22.5. 16 ноября 2010 г.
- ^ «Руководство программиста UNIX, третье издание» . Телефонные лаборатории Белла . Февраль 1973 г. с. qсорт(III). Архивировано из оригинала 24 июля 2023 г. Получено 24 июля 2024 г. - через Общество наследия Unix .
- ^ «Руководство программиста UNIX, четвертое издание» . Телефонные лаборатории Белла . Ноябрь 1973 г. с. qсорт(III). Архивировано из оригинала 24 июля 2023 г. Получено 24 июля 2024 г. - через Общество наследия Unix .
- ^ «qsort(III), из Руководства программиста UNIX, шестое издание» . Юникс-архив . Архивировано из оригинала 25 февраля 2023 г. Проверено 25 сентября 2014 г.
- ^ Макилрой, доктор медицины (10 апреля 1999 г.). «Смертельный противник быстрой сортировки» (PDF) . Программное обеспечение: практика и опыт . 29 (4): 341–344. doi : 10.1002/(SICI)1097-024X(19990410)29:4<341::AID-SPE237>3.0.CO;2-R . S2CID 35935409 . Архивировано (PDF) из оригинала 19 июня 2023 года . Проверено 24 июля 2024 г.
- ^ – FreeBSD функциям библиотеки Руководство по