Как различные языки выполняют сортировку в своих стандартных библиотеках?

Question

Из того, что я прочитал (кратко), Java и Python выглядят так, как будто они используют timsort в своих стандартных библиотеках, тогда как метод сортировки в stdlib C называется qsort, потому что однажды он был quicksort.

Какой алгоритм в настоящее время используют стандартные языки в своих стандартных библиотеках и почему они выбрали этот алгоритм? Кроме того, C отклонился от быстрой сортировки?

Я знаю, что этот вопрос не имеет «актуальных проблем, с которыми я сталкиваюсь», и может показаться открытыми для некоторых, но знание того, как/почему определенные алгоритмы выбраны в качестве стандартных, кажется довольно полезным, но относительно неопытным. Я также чувствую, что в глубине ответа, касающегося проблем, которые зависят от языка (типы данных?) И специфических для машины (кеш-хиты?), Можно было бы лучше понять, как работают разные языки и алгоритмы, чем унифицировать.

Answer 1

библиотека моей машины C обеспечивает qsort, heapsort и mergesort, говоря в man page:

Функции qsort() и qsort_r() являются реализация C.A.R. Алгоритм «quicksort» Хора, вариант сортировки разделов; в частности, см. D.E. Knuth's Алгоритм Q. Quicksort принимает O (n lg n) среднее время. Эта реализация использует медианный выбор, чтобы избежать его O (n) худшее поведение.

heapsort() Функция представляет собой реализацию J.W.J. Алгоритм Уильяма «heapsort», вариант сортировки выбора; в частности, см. D.E. Knuth's Алгоритм H. Heapsort принимает O (n lg n) наихудшее время. Его единственным преимуществом над qsort() является то, что он не использует почти никакой дополнительной памяти; в то время как qsort() не выделяет память, это с использованием рекурсии.

Функция mergesort() требует дополнительной памяти размером nel * width байт; его следует использовать только в том случае, если пространство не стоит на высоте. Функция mergesort() оптимизирована для данных с уже существующим порядком; его наихудшее время - O (n lg n); его лучшим случаем является O (n).

Обычно qsort() быстрее, чем mergesort() который быстрее, чем heapsort(). Доступность памяти и уже существующий порядок в данных могут сделать это неверным.

Есть много библиотек с открытым кодом C, на которые вы можете посмотреть, хотите ли вы увидеть конкретные детали реализации.

Насколько «почему система X выбрала алгоритм Y», это довольно сложный вопрос для значимого ответа - если вам не повезло найти обоснование в документации, вам придется напрямую спросить дизайнеров ,

Answer 2

Я сделал быстрое сканирование в стандарте C11 о qsort(), и я не мог найти никаких упоминаний о том, как qsort() должны быть реализованы и ожидаемое время/пространство сложность алгоритма. Все, что он должен сказать, это о некоторых условиях относительно функции компаратора .

Что это означает, что реализация может выбрать любой алгоритм, основанный на компараторе, который подходит с qsort(). Например, реализация может использовать наивный алгоритм, такой как bubble sort для реализации qsort(), который не так эффективен, как реальный quick sort. Итог заключается в том, что для реализации фактического алгоритма до реализации необходимо принять решение.

Answer 3

C не определяет алгоритм, который будет использоваться qsort.

В текущем glibc (2.17) qsort выделяет память (используя malloc или alloca, если требуемая память действительно мала) и использует алгоритм сортировки слиянием. Если требования к памяти слишком высоки или если malloc не работает, он использует алгоритм быстрой сортировки.

Answer 4

В musl, мы используем Smooth Sort. Концептуально это вариант сортировки кучи (и аналогично времени на месте и O (n log n)), но у него есть приятное свойство, что наихудшая производительность приближается к O (n) для уже отсортированного или почти сортированного ввода. Я не уверен, что это лучший выбор, но очень сложно сделать лучше с помощью локального алгоритма с O (n log n) в худшем случае.

Будучи малоизвестным изобретением Дийкстры, он также делает его прохладным. :-)