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

StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»

2011-06-13T17:43:15Z

Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»

Внесённые изменения

WikiSysop: 1 версия

2008-10-23T16:47:57Z

1 версия

StasFomin: обновление данных

2008-10-22T15:39:05Z

обновление данных

WikiSysop: 1 версия

2008-08-04T09:55:52Z

1 версия

BenderBot: реплицировано из внутренней CustisWiki

2005-10-17T17:15:17Z

реплицировано из внутренней CustisWiki

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

Алгоритм быстрой сортировки (''QuickSort'') является популярным алгоритмом для [[сортировка|сортировки]], несмотря на то, что в худшем случае (на некоторых входных массивах) использует время <math>\Omega(n^2)</math>, что, например, хуже, чем сложность в наихудшем случае алгоритма [[Сортировка слиянием]]. Дело в том, что анализ «в среднем» и опыт реального использования показали его эффективность.

== Быстрая сортировка с детерминированным выбором оси ==

Ключевая идея алгоритма заключается в процедуре «partition», которая за линейное время от размера массива, осуществляет такую перестановку элементов, относительно некоторой «оси» — заданного значения, равного одному из значений сортируемого интервала массива, что переставленный массив состоит из трех интервалов, идущих по порядку:

# Элементы меньшие «оси»
# Элементы равные «оси»
# Элементы большие «оси»

Первый и последний из упомянутых интервалов могут быть неупорядоченными,
поэтому далее, они рекурсивно сортируются процедурой «quicksort_interval».

Реализация на [[Python]] (и пример работы) алгоритма «Быстрая сортировка с детерминированным выбором оси»:

<code-python>
def quicksort(A):

def swap(i,j): # Перестановка i-го и j-го элементов массива A
temp = A[i]; A[i] = A[j]; A[j] = temp

#Перестановка элементов в интервале [left:right) массива А,
# таким образом, что, возникают три интервала:
# в первой части массива все элементы < осевого значения pivotValue
# а во второй = осевому значению.
# а во третьей > осевого значения.
def partition(left, right, pivotValue):
print funcname() ,A[left:right], pivotValue,
indexLow = i = left # Нижний и текущий индексы
indexHigh = right-1 # Верхний индекс
while i <= indexHigh: # Пока есть область не просмотренных элементов.
if A[i] < pivotValue: # Если элемент меньше оси
swap(i,indexLow) # гоним его в начало интервала
indexLow = indexLow + 1 # сужаем область слева
i = i + 1
elif A[i] > pivotValue: # Если элемент больше оси
swap(i,indexHigh) # гоним его в конец интервала
indexHigh = indexHigh - 1 # сужаем область справа
else: # A[i]=pivotValue
i = i + 1 # сужаем область слева
print "->", A[left:indexLow],A[indexLow:indexHigh+1],A[indexHigh+1:right]
return (indexLow,indexHigh)

def quicksort_interval(left, right):
if right > left+1: # Если в интервале [left:right) хотя бы два элемента
print funcname(), A[left:right]
(indexLow,indexHigh) = partition(left, right, A[left])
quicksort_interval(left, indexLow)
quicksort_interval(indexHigh+1, right)

quicksort_interval(0, len(A))
return A
</code-python>

Sorting: [3, 1, 4, 1, 5, 9, 2, 6, 3, 5, 8, 7]
quicksort_interval: [3, 1, 4, 1, 5, 9, 2, 6, 3, 5, 8, 7]
partition: [3, 1, 4, 1, 5, 9, 2, 6, 3, 5, 8, 7] 3 -> [1, 1, 2] [3, 3] [9, 6, 5, 5, 8, 7, 4]
quicksort_interval: [1, 1, 2]
partition: [1, 1, 2] 1 -> [] [1, 1] [2]
quicksort_interval: [9, 6, 5, 5, 8, 7, 4]
partition: [9, 6, 5, 5, 8, 7, 4] 9 -> [6, 5, 5, 8, 7, 4] [9] []
quicksort_interval: [6, 5, 5, 8, 7, 4]
partition: [6, 5, 5, 8, 7, 4] 6 -> [5, 5, 4] [6] [7, 8]
quicksort_interval: [5, 5, 4]
partition: [5, 5, 4] 5 -> [4] [5, 5] []
quicksort_interval: [7, 8]
partition: [7, 8] 7 -> [] [7] [8]
Sorted: [1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 9]

Эффективность алгоритма существенно зависит от выбора «оси». Например, если назначать «осью» значение, которое больше или меньше всех элементов, то алгоритм вовсе не будет работать — разбиение никак не будет уменьшать сортируемый интервал и алгоритм зациклиться.

В представленном выше алгоритме «осью» назначается первый элемент в разбиваемом интервале. Для некоторых последовательностей, это может приводить к неоптимальному поведению, когда при разбиении, один из крайних интервалов сильно меньше другого, или вовсе пустой.
Например, такой «плохой» входной последовательностью будет следующая:

Sorting: [1, 6, 2, 5, 3, 7, 4]
quicksort_interval: [1, 6, 2, 5, 3, 7, 4]
partition: [1, 6, 2, 5, 3, 7, 4] 1 -> [] [1] [2, 5, 3, 7, 4, 6]
quicksort_interval: [2, 5, 3, 7, 4, 6]
partition: [2, 5, 3, 7, 4, 6] 2 -> [] [2] [3, 7, 4, 6, 5]
quicksort_interval: [3, 7, 4, 6, 5]
partition: [3, 7, 4, 6, 5] 3 -> [] [3] [4, 6, 5, 7]
quicksort_interval: [4, 6, 5, 7]
partition: [4, 6, 5, 7] 4 -> [] [4] [5, 7, 6]
quicksort_interval: [5, 7, 6]
partition: [5, 7, 6] 5 -> [] [5] [6, 7]
quicksort_interval: [6, 7]
partition: [6, 7] 6 -> [] [6] [7]
Sorted: [1, 2, 3, 4, 5, 6, 7]

Видно, что на каждой рекурсии, сортируемый интервал уменьшается только на один осевой элемент. Таким образом, алгоритм на «плохих» входных данных выполняет <math>\Omega(N)</math> рекурсий, а общее количество операций (с учетом операций в процедуре «partition» ) будет
<math>\Omega(\sum_{i=1}^{N} i)=\Omega(n^2)</math>.

Осталось выяснить, часто ли встречаются наихудшие случаи на множестве входных данных.

Допустим, входные данные случайны, и их распределение таково,
что в каждом интервале длины ''N'' попадаемом в процедуру «partition», первый элемент с равной вероятностью может быть ''k''-тым (''1 <= k <= N''), по величине, "разбивая", тем самым входной интервал на интервалы длины ''k-1'' и ''N-k-1''. Тогда можно записать следующую рекурсивную оценку матожидания сложности алгоритма:
<math>
T(N) \leq O(N)+\frac{1}{N}(\sum_{k=1}^{N} T(k-1)+T(N-k-1) \leq O(N)+\frac{2}{N}\sum_{k=1}^{N-1} T(k)
</math>

Анализ показывает, что при этом предположении (достаточно равномерном распределении входных данных), справедливо матожидание времени работы, асимптотически оптимальное минимальной сложности сортировки:
<math>
T(N)=O(N\log N)
</math>

== Быстрая сортировка с вероятностным выбором оси ==

К сожалению, допущенное в предыдущем разделе предположение о равномерности распределения «осей» относительно интервалов, может не встречаться на практике. Например, есть вариации детерминированного алгоритма, для которых «плохими» будут уже отсортированные (или почти отсортированные) последовательности, а таковые часто встречаются в реальных задачах. В таких случаях, когда нельзя «сделать случайными» входные данные, можно внести «элемент случайности» непосредственно в сам алгоритм. В частности, чтобы сохранилась оптимальная оценка матожидания, достаточно сделать вероятностным выбор осевого элемента из разделяемого интервала.

Вероятностный алгоритм отличается от детерминированного, только строчкой, где задается выбор вероятностный выбор осевого элемента, однако, как мы увидели, это дает ему возможность «избегать потерь» на входных данных, которые были «наихудшими» для детерминированного алгоритма, и достигнуть оценки матожидания времени работы ''O(N log N)'', вне зависимости от входных данных.

Реализация на [[Python]] (и пример работы) алгоритма «Быстрая сортировка с вероятностным выбором оси»:

<code-python>
def quicksort(A):

def swap(i,j): # Перестановка i-го и j-го элементов массива A
temp = A[i]; A[i] = A[j]; A[j] = temp

#Перестановка элементов в интервале [left:right) массива А,
# таким образом, что, возникают три интервала:
# в первой части массива все элементы < осевого значения pivotValue
# а во второй = осевому значению.
# а во третьей > осевого значения.
def partition(left, right, pivotValue):
print funcname() ,A[left:right], pivotValue,
indexLow = i = left # Нижний и текущий индексы
indexHigh = right-1 # Верхний индекс
while i <= indexHigh: # Пока есть область не просмотренных элементов.
if A[i] < pivotValue: # Если элемент меньше оси
swap(i,indexLow) # гоним его в начало интервала
indexLow = indexLow + 1 # сужаем область слева
i = i + 1
elif A[i] > pivotValue: # Если элемент больше оси
swap(i,indexHigh) # гоним его в конец интервала
indexHigh = indexHigh - 1 # сужаем область справа
else: # A[i]=pivotValue
i = i + 1 # сужаем область слева
print "->", A[left:indexLow],A[indexLow:indexHigh+1],A[indexHigh+1:right]
return (indexLow,indexHigh)

def quicksort_interval(left, right):
if right > left+1: # Если в интервале [left:right) хотя бы два элемента
print funcname(), A[left:right]
(indexLow,indexHigh) = partition(left, right, A[RandomSource.randrange(left, right)])
quicksort_interval(left, indexLow)
quicksort_interval(indexHigh+1, right)

RandomSource = random.Random(6666) # Инициализируем генератор случайных чисел.
quicksort_interval(0, len(A))
return A
</code-python>

Sorting: [1, 6, 2, 5, 3, 7, 4]
quicksort_interval: [1, 6, 2, 5, 3, 7, 4]
partition: [1, 6, 2, 5, 3, 7, 4] 6 -> [1, 2, 5, 3, 4] [6] [7]
quicksort_interval: [1, 2, 5, 3, 4]
partition: [1, 2, 5, 3, 4] 2 -> [1] [2] [3, 4, 5]
quicksort_interval: [3, 4, 5]
partition: [3, 4, 5] 4 -> [3] [4] [5]
Sorted: [1, 2, 3, 4, 5, 6, 7]
== Реализация на pl/sql ==
[[Участник:Mikle Zaborov|Mikle Zaborov]] 12:34, 17 Oct 2005 (MSD)
<code-oracle8>
_public_procedure({quick_sort},{
_param({at_arr}, {IN OUT NOCOPY pk_cmn.TNumberArray},, {массив чисел})
},{Отсортировать массив быстрой сортировкой},
{
AS
PROCEDURE swap(i INTEGER,j INTEGER)
AS
l Integer;
BEGIN
l:=at_arr(i);
at_arr(i):=at_arr(j);
at_arr(j):=l;
END;
PROCEDURE QuickSort(a_Lo INTEGER,a_Hi INTEGER)
AS
Lo INTEGER;
Hi INTEGER;
Mid INTEGER;
BEGIN
Lo := a_Lo;
Hi := a_Hi;
Mid := at_arr(TRUNC((Lo + Hi)/2));
LOOP
WHILE at_arr(Lo) < Mid LOOP Lo:=Lo+1; END LOOP;
WHILE at_arr(Hi) > Mid LOOP Hi:=Hi-1; END LOOP;
IF Lo <= Hi THEN
Swap(Lo, Hi);
Lo:=Lo+1;
Hi:=Hi-1;
END IF;
EXIT WHEN Lo > Hi;
END LOOP;
if Hi > a_Lo then QuickSort(a_Lo, Hi); END IF;
if Lo < a_Hi then QuickSort(Lo, a_Hi); END IF;
END;
BEGIN
QuickSort(at_arr.first,at_arr.last);
END;
},{})
</code-oracle8>

[[Category:Алгоритмы]]
{{replicate-from-custiswiki-to-lib}}

Mikle Zaborov в 08:34, 17 октября 2005

2005-10-17T08:34:04Z

← Предыдущая	Версия 09:55, 4 августа 2008
(не показана 1 промежуточная версия 1 участника)
(нет различий)

← Предыдущая	Версия 16:47, 23 октября 2008
(нет различий)

@@ Строка 1: / Строка 1: @@
-Алгоритм быстрой сортировки (''QuickSort'') является популярным алгоритмом для [[сортировка|сортировки]], несмотря на то, что в худшем случае (на некоторых входных массивах) использует время <math>\Omega(n^2)</math>, что, например, хуже, чем сложность в наихудшем случае алгоритма [[Сортировка слиянием]]. Дело в том, что анализ «в среднем» и опыт реального использования показали его эффективность.
+Алгоритм быстрой сортировки (''QuickSort'') является популярным алгоритмом для [[сортировка|сортировки]], несмотря на то, что в худшем случае (на некоторых входных массивах) использует время <m>\Omega(n^2)</m>, что, например, хуже, чем сложность в наихудшем случае алгоритма [[Сортировка слиянием]]. Дело в том, что анализ «в среднем» и опыт реального использования показали его эффективность.
@@ Строка 90: / Строка 90: @@
   Sorted:    [1, 2, 3, 4, 5, 6, 7]
-Видно, что на каждой рекурсии, сортируемый интервал уменьшается только на один осевой элемент. Таким образом, алгоритм на «плохих» входных данных выполняет <math>\Omega(N)</math> рекурсий, а общее количество операций (с учетом операций в процедуре «partition» ) будет
+Видно, что на каждой рекурсии, сортируемый интервал уменьшается только на один осевой элемент. Таким образом, алгоритм на «плохих» входных данных выполняет <m>\Omega(N)</m> рекурсий, а общее количество операций (с учетом операций в процедуре «partition» ) будет
-<math>\Omega(\sum_{i=1}^{N} i)=\Omega(n^2)</math>.
+<m>\Omega(\sum_{i=1}^{N} i)=\Omega(n^2)</m>.
 Осталось выяснить, часто ли встречаются наихудшие случаи на множестве входных данных.
@@ Строка 97: / Строка 97: @@
 Допустим, входные данные случайны, и их распределение таково,
 что в каждом интервале длины ''N'' попадаемом в процедуру «partition», первый элемент с равной вероятностью может быть ''k''-тым (''1 <= k <= N''), по величине, "разбивая", тем самым входной интервал на интервалы длины ''k-1'' и ''N-k-1''. Тогда можно записать следующую рекурсивную оценку матожидания сложности алгоритма:
-<math>
+<m>
   T(N) \leq  O(N)+\frac{1}{N}(\sum_{k=1}^{N} T(k-1)+T(N-k-1) \leq O(N)+\frac{2}{N}\sum_{k=1}^{N-1} T(k)
-</math>
+</m>
 Анализ показывает, что при этом предположении (достаточно равномерном распределении входных данных), справедливо матожидание времени работы, асимптотически оптимальное минимальной сложности сортировки:
-<math>
+<m>
    T(N)=O(N\log N)
-</math>
+</m>

← Предыдущая	Версия 08:34, 17 октября 2005
(нет различий)