Ответы:
В произвольном случае — 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 лет назад