Быстрая сортировка :: Quick sort

Тони Хоар в 60-х
Простой в реализации и очень быстрый способ. Считается эталоном скорости для алгоритмов сортировки. Когда заходит о временной сложности какого-либо эффективного метода сортировки, то обычно его сравнивают именно с Quick sort.

Способ разработал 26-летний аспирант из Оксфорда Чарльз Хоар. В том далёком 1960 году он стажировался в СССР. В МГУ он обучался компьютерному переводу, а в школе Колмогорова изучал теорию вероятности.

Придурковатая сортировка

Алгоритм

  1. Выбирается опорный элемент (например, посередине массива).
  2. Массив просматривается слева-направо и производится поиск ближайшего элемента, больший чем опорный.
  3. Массив просматривается справа-налево и производится поиск ближайшего элемента, меньший чем опорный.
  4. Найденные элементы меняются местами.
  5. Продолжается одновременный двухсторонний просмотр по массиву с последующими обменами в соответствии с пунктами 2-4.
  6. В конце концов, просмотры слева-напрво и справа-налево сходятся в одной точке, которая делит массив на два подмассива.
  7. К каждому из двух подмассивов рекурсивно применяется «Быстрая сортировка».

Характеристики алгоритма

Название Быстрая сортировка (Quick sort)
Автор Сэр Чарльз Э́нтони Ри́чард Хо́ар
(Sir Charles Antony Richard Hoare)
Год 1960
Класс Сортировки обменами
Устойчивость Нет
Сравнения Да
Сложность по времени Лучшая O(n)
Средняя O(n log n)
Худшая O(n2)
Сложность по дополнительной памяти Нативная O(n)
Седжвик O(log n)

Ссылки

Быстрая сортировка в Википедии
Quick sort on Wikipedia
Реализация на различных ЯП

Добавить комментарий