C: Что такое временная сложность функции qsort?

Question

Какова сложность функции qsort из стандартной библиотеки в C? Если возможно, предоставьте также ссылку.

#include <stdlib.h> 
    void qsort(void *base, size_t nmemb, size_t size, 
    int (*compar)(const void *, const void *)); 

Answer 1

Согласно cppreference.com, который является достаточно надежным источником для документации о языке C:

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

У меня есть проект стандарта C ISO, в котором говорится следующее о qsort:

Функция QSort сортирует массив nmemb объектов, начальный элемент которого, на который указывает основание. Размер каждого объекта определяется размером.

Содержимое массива сортируется в порядке возрастания в соответствии с сопоставлением функции , на которую указывает сравнение, которая вызывается с двумя аргументами, которые указывают на сравниваемые объекты . Функция должна возвращать целое число меньше, чем, или больше нуля, если первый аргумент считается меньше, чем, или больше второго.

Если два элемента сравниваются как равные, их порядок в результирующем отсортированном массиве не указан.

Возвращает:

Функция QSort не возвращает никакого значения.

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

В общем случае вы не можете предположить, что время выполнения будет O (n log n) в среднем или в худшем случае. Существует история реализаций, которые используют эвристику, которая может выродиться в худшем случае; Для получения дополнительной информации, найдите «Противник убийц для Quicksort».

Сравните это с C++ std::sort, which is guaranteed to run in time O(n log n) в наихудшем случае.