Предоставляет ли функция qsort() гарантии производительности?
Требует ли стандарт C, чтобы функция стандартной библиотеки qsort() обеспечивала определенный уровень производительности? Название предполагает использование алгоритма O(n log n), такого как быстрая сортировка . Может ли библиотека, соответствующая стандартам, реализовать это с помощью сортировки вставкой O(n^2) или даже богосортировки O(n!)?
TL;DR: Нет qsort (т. е. quicksort) может быть O(n log n), но в худшем случае это может быть O(n^2). mergesort — это всегда O(n log n) время с O(n) [дополнительным] пространством. Обратите внимание, что qsort в некоторых системах использует сортировку вставками на нижних уровнях (на основе эвристики). Итак, ответ: «Это зависит»
Посмотрите исходный код qsort(). Это сочетание методов сортировки, оптимизированное для предотвращения наихудших сценариев, присущих быстрой сортировке. Вы не можете сделать намного лучше.
Я не думаю, что он также определяет верхний предел используемого дополнительного пространства. Кто-нибудь, пожалуйста, поправьте меня, если я ошибаюсь.
Спецификация очень проста. Здесь ничего не говорится о сложности ни памяти, ни времени.
Точно так же имя bsearch() предполагает, что он будет выполнять двоичный поиск, и спецификация функции сравнения позволяет это, но фактических требований к этому нет.
Реализация может генерировать любой код, который ей нравится, при условии, что выходные данные удовлетворяют требованиям стандарта C. Конечно, компилятор будет использовать лучшие методы, имеющиеся в его распоряжении, потому что ему нужна хорошая репутация.
Это то, что люди в сообществе стандартизации называют проблемой «качества реализации». Нет необходимости законодательно закреплять это в спецификации, рынок отсеет плохие проекты. Более того, сортировка — это хорошо изученная технология, и библиотекам нет оправдания использованию плохого алгоритма.
На практике очень часто это основано на Разработке функции сортировки, Bentley 1993 .
Вместо «производительности» вы можете использовать такие термины, как «сложность времени выполнения» или «сложность пространства», чтобы более точно обсудить, какие аспекты масштабируемости вас интересуют.
Ответы 1
Согласно стандартам C89, C99, C11 и C17, никакого особого поведения big-O не требуется.
Это язык стандарта C89 под заголовком 7.10.5.2. Остальные стандарты содержат идентичные формулировки.
Краткое содержание
#include <stdlib.h> void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));Описание
Функция qsort сортирует массив объектов nmemb, на начальный элемент которого указывает база. Размер каждого объекта определяется размером.
Содержимое массива сортируется по возрастанию в соответствии с функцией сравнения, на которую указывает функция сравнения, которая вызывается с двумя аргументами, указывающими на сравниваемые объекты. Функция должна возвращать целое число меньше, равное или большее нуля, если считается, что первый аргумент соответственно меньше, равен или больше второго.
Если два элемента сравниваются как равные, их порядок в отсортированном массиве не указан.
Возврат
Функция qsort не возвращает значения.
Стандарт не определяет конкретный алгоритм или конкретную скорость. Фактически, он делает все возможное, чтобы использовать больше алгоритмов сортировки, не требуя стабильной сортировки. Я понимаю, что это означает, что Bogosort — это совместимый со стандартами способ реализации qsort.
Нет, здесь не указан метод сортировки или производительность.