Быстрая сортировка :: 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

Реализация на различных ЯП