Быстрая сортировка (Quicksort)

Алгоритм использует подход разделяй и властвуй.

Алгоритм

Выбрать опорный элемент
Разделить массив на две части: одна из элементов меньше опорного и остальные
Для двух частей повторить алгоритм
Соединить массив — первая часть, опорный элемент, вторая часть

Сложность

Сложность в среднем и в худшем $\mathcal{O}(n\ast lo{g}_2(n))$ $\mathcal{O}(n^2)$

Ссылки

• Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 4. Быстрая сортировка. Быстрая сортировка

Ссылки на эту заметку

Эта заметка на GitHub

Обсудить на форуме