Быстрая сортировка

Описание	Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в СТУ в 1960 году.Один из самых быстрых известных универсальных алгоритмов сортировки массивов.
Область знаний	Информатика
Область использования (ISTE)	Computational Thinker
Возрастная категория	12
Поясняющее видео
Близкие рецепту понятия
Среды и средства для приготовления рецепта:

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена - Сортировка пузырьком, известного в том числе своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы (таким образом улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов). Псевдокод:

algorithm quicksort(A, lo, hi) is
   if lo < hi then
       p:= partition(A, lo, hi)
       quicksort(A, lo, p)
       quicksort(A, p + 1, hi)
algorithm partition(A, low, high) is
   pivot:= A[(low + high) / 2]
   i:= low
   j:= high
   loop forever
       
       while A[i] < pivot 
              i:= i + 1
       while A[j] > pivot
              j:= j - 1
       if i >= j then
           return j
       swap A[i++] with A[j--]

Image