Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Даёт в среднем O(nlog(n)) обменов при упорядочении n элементов. В худшем случае, однако, получается O(n²) обменов, Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(nlog(n)), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время. Интересно, что Хоар разработал этот метод применительно к машинному переводу: дело в том, что в то время словарь хранился на магнитной ленте, и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты.

2008-10-10 • Просмотров [ 4005 ]