Изменения

Перейти к: навигация, поиск

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

95 байт добавлено, 22:28, 7 июня 2014
→‎Псевдокод
==Псевдокод==
<wikitex> function Quicksort(A, l, r) '''if ''' l < r then q = Partition(A, l, r) Quicksort(A, l, q - 1) Quicksort(A, q + 1, r)</wikitex>
Для сортировки всего массива необходимо выполнить процедуру <tex>Quicksort(A, 0, length[A] - 1)</tex>.
===Разбиение массива===
Основной шаг алгоритма сортировки {{---}} процедура <tex>Partition</tex>, которая переставляет элементы массива <tex>A[p..r]</tex> нужным образом:
<wikitex> Partition(A, l, r) x = A[l] i = l j = r '''while ''' true do '''while ''' A[i] < x do i = i + 1 '''while ''' A[j] > x do j = j - 1 '''if ''' i < j then поменять swap(A[i] и ,A[j]) '''else ''' '''return ''' j</wikitex>
==Асимптотика==
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/37986»

Навигация