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

Алгоритм быстрой сортировки является популярным алгоритмом для сортировки, несмотря на то, что в худшем случае (на некоторых входных массивах) использует время $\Omega(n^2)$, что, например, хуже, чем сложность в наихудшем случае алгоритма сортировки слиянием. Дело в том, что анализ «в среднем» и опыт реального использования показали его эффективность.

Описание алгоритма

• На языке программирования Глагол:

 ЗАДАЧА Упорядочить-(ряд+:РЯД ИЗ Доступ; всего:ЦЕЛ; сравнить:ЗАДАЧА(с1-,с2-:Вид):ЦЕЛ);
 ПЕР
   Л,П:ЦЕЛ;        (* текущий участок                   *)
   л,п:ЦЕЛ;        (* новый участок                     *)
   граница:Доступ; (* граничное значение для разделения *)
   рядл:Доступ;    (* промежуточное значение для обмена *)
   глубина:ЦЕЛ;    (* текущая глубина стека             *)
   (* стек для новых участков *)
   стек:РЯД 32 ИЗ НАБОР Л,П:ЦЕЛ КОН; 
 УКАЗ
   глубина:=0; 
   стек[глубина].Л:=0; 
   стек[глубина].П:=всего-1;
   ПОВТОРЯТЬ
     (* выбор из стека последнего запроса *)
     Л:=стек[глубина].Л; 
     П:=стек[глубина].П;
     УМЕНЬШИТЬ(глубина);
     ПОВТОРЯТЬ
       (* разделение ряд[Л]...ряд[П] *)
       л:=Л; п:=П;
       граница:=ряд[(Л+П) ДЕЛИТЬ 2];
       ПОВТОРЯТЬ
         ПОКА сравнить(ряд[л]^,граница^) < 0 ВЫП УВЕЛИЧИТЬ(л) КОН;
         ПОКА сравнить(граница^,ряд[п]^) < 0 ВЫП УМЕНЬШИТЬ(п) КОН;
         ЕСЛИ л <= п ТО (* обмен ряд[л] с ряд[п] *)
           рядл:=ряд[л];
           ряд[л]:=ряд[п];
           ряд[п]:=рядл;
           УВЕЛИЧИТЬ(л);
           УМЕНЬШИТЬ(п)
         КОН
       ДО л > п;
       ЕСЛИ п-Л < П-л ТО
         ЕСЛИ л < П ТО (* запись в стек запроса на упорядочивание правой части *)
           УВЕЛИЧИТЬ(глубина);
           стек[глубина].Л:=л;
           стек[глубина].П:=П
         КОН;
         П:=п (* продолжение упорядочивания левой части *)
       ИНАЧЕ
         ЕСЛИ Л < п ТО (* запись в стек запроса на упорядочивание левой части *)
           УВЕЛИЧИТЬ(глубина);
           стек[глубина].Л:=Л;
           стек[глубина].П:=п
         КОН;
         Л:=л (* продолжение упорядочивания правой части *)
       КОН
     ДО Л >= П
   ДО глубина < 0
 КОН Упорядочить;

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

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

1. Элементы меньшие «оси»
2. Элементы равные «оси»
3. Элементы большие «оси»

Первый и последний из упомянутых интервалов могут быть неупорядоченными, поэтому далее, они рекурсивно сортируются процедурой «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]

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

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

Допустим, входные данные случайны, и их распределение таково, что в каждом интервале длины N попадаемом в процедуру «partition», первый элемент с равной вероятностью может быть k-тым (1 <= k <= N), по величине, «разбивая», тем самым входной интервал на интервалы длины k-1 и N-k-1. Тогда можно записать следующую рекурсивную оценку матожидания сложности алгоритма: $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)$

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

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

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

Вероятностный алгоритм отличается от детерминированного, только строчкой, где задается выбор вероятностный выбор осевого элемента, однако, как мы увидели, это дает ему возможность «избегать потерь» на входных данных, которые были «наихудшими» для детерминированного алгоритма, и достигнуть оценки математического ожидания времени работы 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]

Литература

По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.