Быстрая сортировка: различия между версиями
Материал из Поле цифровой дидактики
Patarakin (обсуждение | вклад) |
Patarakin (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
{{Scripting Tutorials | {{Scripting Tutorials | ||
|Description=Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в СТУ в 1960 году.Один из самых быстрых известных универсальных алгоритмов сортировки массивов. | |Description=Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в СТУ в 1960 году.Один из самых быстрых известных универсальных алгоритмов сортировки массивов. | ||
|Field_of_knowledge=Информатика | |Field_of_knowledge=Информатика | ||
|FieldActivity=Computational Thinker | |FieldActivity=Computational Thinker | ||
Строка 27: | Строка 25: | ||
'''return''' j | '''return''' j | ||
'''swap''' A[i++] '''with''' A[j--] | '''swap''' A[i++] '''with''' A[j--] | ||
== Image == | |||
https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif |
Текущая версия на 17:48, 9 ноября 2023
Описание | Быстрая сортировка, сортировка Хоара (англ. 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