Какой самый быстрый алгоритм сортировки?

интернет компьютеры программирование алгоритмы

Нужен алгоритм сортировки. Самый быстрый.

Примечание:
Лучше несколько.

Примечание:
Тогда нужен самый маложрущий память.

Примечание:
Если верить Вики, то quicksort в некоторых случаях очень хорошо ее хавает
Ответы:
В произвольном случае — qsort.
Если же исходные данные имеют какой-то неслучайный порядок, то нужно думать в соответствии с конкретной ситуацией.
Самого быстрого не существует.
Прочитайте 3 тома "Искусства программирования" Дональда Кнута - там на трёх тысячах страниц это обсуждается. :) И в конце вывод что в общем случае нифига самого быстрого выбрать нельзя. Зависит от ситуации.
По поводу "самый маложрущий память" - большинство алгоритмов сортировки выделяют 1-2 переменных того типа, который сортируется. Т.е. говорить о затратах памяти как-то странно. Промежуточные массивы или выделение блоков данных в памяти по-моему, не используются нигде.
Все хорошие алгоритмы сортировки работают за время O(n*log(n))
Самые известные - это сортировка слиянием, сортировки кучей и быстрой сортировки.
Быстрая сортировка в самом плохом случае выполняется дольше, за O(n*n) операций, но в среднем - все те же O(n*log(n))
Мне больше всего понравился этот "алгоритм", называется Bead Sort :)
Понравился физической реализацией.
Вы лучше тип данных правильнее подберите - оно само собой как-то быстрее получается, безо всяких волшебных алгоритмов.
Если придется сортировать содержимое файлов большого размера (не влезающие в память), то уже совсем другие методы.
А так, конечно, qsort. Стоит отметить, что на современных процессорах его лучше реализовывать в несколько процессов.
Для больших файлов наверное лучший метод - сортировка слиянием.
В древности его даже на магнитных лентах использовали.
(бобина на входе, сортированная бобина на выходе, и несколько промежуточных лент :))
qsort требует логарифмической памяти всегда и в традиционном исполнении он работает в зудшем случае за квадратичное время. Можно модифицировать выбор медиан, так, чтобы он работал за минимально возможное время nlog n.
Правда, что ни один не выделяет явно доп. память. Дело вот в чём, на примере Хоара: там традиционно две рекурсии, одна хвостовая и её можно устранить. Но вторая рекурсия неустранима, и за время работы произойдёт O(log n) рекурсивных вызовов (в среднем). Значит надо будет хранить одновременно O(log n) адресов возврата.
Если мне не изменяет память то QuickSort можно реализовать 3мя вложенными циклами с командами прерывания цикла - соответственно рекурсии нет - память не жрет.


16 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.