Быстрая сортировка - История изменений

Patarakin в 14:48, 9 ноября 2023

2023-11-09T14:48:19Z

← Предыдущая версия		Версия от 17:48, 9 ноября 2023
Строка 1:		Строка 1:
	{{Scripting Tutorials		{{Scripting Tutorials
	\|Description=Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в СТУ в 1960 году.Один из самых быстрых известных универсальных алгоритмов сортировки массивов.		\|Description=Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в СТУ в 1960 году.Один из самых быстрых известных универсальных алгоритмов сортировки массивов.

	~~https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif~~
	\|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

Patarakin в 14:47, 9 ноября 2023

2023-11-09T14:47:41Z

← Предыдущая версия		Версия от 17:47, 9 ноября 2023
Строка 6:		Строка 6:
	\|FieldActivity=Computational Thinker		\|FieldActivity=Computational Thinker
	\|Возрастная категория=12		\|Возрастная категория=12
	~~\|Environment=Snap!~~
	}}		}}
	QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена - [[Сортировка пузырьком]], известного в том числе своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы (таким образом улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов).		QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена - [[Сортировка пузырьком]], известного в том числе своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы (таким образом улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов).

Patarakin: Новая страница: «{{Scripting Tutorials |Description=Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в СТУ в 1960 году.Один из самых быстрых известных универсальных ал...»

2022-12-15T17:17:24Z

Новая страница: «{{Scripting Tutorials |Description=Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в СТУ в 1960 году.Один из самых быстрых известных универсальных ал...»

Новая страница

{{Scripting Tutorials
|Description=Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в СТУ в 1960 году.Один из самых быстрых известных универсальных алгоритмов сортировки массивов.

https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif
|Field_of_knowledge=Информатика
|FieldActivity=Computational Thinker
|Возрастная категория=12
|Environment=Snap!
}}
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--]