WikiDer > Qsort

Qsort

qsort это Стандартная библиотека C функция, которая реализует полиморфный алгоритм сортировки для массивов произвольных объектов в соответствии с предоставленной пользователем функцией сравнения. Он назван в честь алгоритма «более быстрой сортировки» ( быстрая сортировка вариант, принадлежащий Р. С. Скоуэну), который изначально использовался для его реализации в Unix Библиотека C, хотя стандарт C не требует, чтобы она реализовывала быструю сортировку.[1]

Реализации функции qsort достигают полиморфизм, возможность сортировать различные типы данных, принимая указатель на функцию к трехстороннее сравнение функция, а также параметр, определяющий размер отдельных входных объектов. В Стандарт C требует, чтобы функция сравнения реализовала общий заказ на элементах входного массива.[2]

История

Функция qsort была реализована Ли МакМахон в 1972 г.[3][1] Это было на месте в Версия 3 Unix как библиотечная функция, но тогда была ассемблер подпрограмма.[3]

Версия C, примерно с интерфейсом стандартной версии C, была на месте в Версия 6 Unix.[4]Он был переписан в 1983 году для BSD.[1]Функция была стандартизирована в ANSI C (1989).

В 1991 году сотрудники Bell Labs заметили, что версии qsort McMahon и BSD потребляют квадратичное время для некоторых простых входов. Таким образом Джон Бентли и Дуглас Макилрой разработал новую более быструю и надежную реализацию.[1]

Пример

Следующий фрагмент кода C показывает, как отсортировать список целых чисел с помощью qsort.

#включают <stdlib.h>/ * Функция сравнения. Получает два общих (недействительных) указателя на сравниваемые элементы. * /int compare_ints(const пустота *п, const пустота *q) {    int Икс = *(const int *)п;    int у = *(const int *)q;    / * Избегайте возврата x - y, что может вызвать неопределенное поведение       из-за целочисленного переполнения со знаком. * /    если (Икс < у)        возвращаться -1;  // Возвращаем -1, если хотите по возрастанию, 1, если хотите по убыванию.     еще если (Икс > у)        возвращаться 1;   // Верните 1, если хотите по возрастанию, -1, если хотите по убыванию.     возвращаться 0;    // Вся логика часто альтернативно записывается:    возвращаться (Икс > у) - (Икс < у);}/ * Сортируем массив из n целых чисел, на который указывает a. * /пустота sort_ints(int *а, size_t п) {    qsort(а, п, размер(*а), compare_ints);}

Рекомендации

  1. ^ а б c d Бентли, Джон Л .; Макилрой, М. Дуглас (1993). «Разработка функции сортировки». Программное обеспечение - практика и опыт. 23 (11): 1249–1265. CiteSeerX 10.1.1.14.8162. Дои:10.1002 / spe.4380231105.
  2. ^ ISO / IEC 9899: 201x, Языки программирования - C (черновик). §7.22.5. 16 ноября 2010 г.
  3. ^ а б "qsort (III), из Руководства программиста UNIX, третье издание". Архив Unix.
  4. ^ "qsort (III), из Руководства программиста UNIX, шестое издание". Архив Unix.