Быстрая сортировка: различия между версиями
Материал из Поле цифровой дидактики
Patarakin (обсуждение | вклад) (Новая страница: «{{Scripting Tutorials |Description=Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в СТУ в 1960 году.Один из самых быстрых известных универсальных ал...») |
Patarakin (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 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 | ||
|Возрастная категория=12 | |Возрастная категория=12 | ||
}} | }} | ||
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена - [[Сортировка пузырьком]], известного в том числе своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы (таким образом улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов). | QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена - [[Сортировка пузырьком]], известного в том числе своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы (таким образом улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов). | ||
| Строка 28: | Строка 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
