Быстрая сортировка
Материал из Поле цифровой дидактики
Описание | Быстрая сортировка, сортировка Хоара (англ. 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