Описание тега qsort

Описание тега Вопросы с тегом
NoneQsort - это имя стандартной библиотечной функции C, которая сортирует массивы с помощью функции сравнения, предоставляемой вызывающей стороной. Другие языки программирования могут предоставлять аналогичные функции под тем же именем. Несмотря на название, эти функции не обязательно реализуют быструю сортировку, поэтому используйте тег [quicksort] вместо этого для вопросов, касающихся конкретно этого алгоритма. Используйте [qsort] ТОЛЬКО для вопросов о библиотечных функциях с таким именем.

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

Хотя название наводит на мысль о "Быстрой сортировке" Хоара, эти функции не обязательно реализуют какие-либо вариации этого алгоритма. В частности, прототипный пример - C - не требуется стандартом этого языка для реализации какого-либо конкретного алгоритма.

С другой стороны, qsortспецификации функций обычно согласуются с реализацией Quick Sort. Например, они обычно не указываются как стабильные сорта, а C, в частности, не указывается как стабильные. (Стандартная быстрая сортировка нестабильна.)

На практике было бы удивительно встретить qsort функция без этих свойств, общих с реализациями быстрой сортировки:

  • сортировка на месте с накладными расходами не более O(log n) в среднем случае.
  • производительность ограничена O(n log n) в среднем случае и не хуже, чем O(n2) в худшем случае.