Быстрая сортировка — различия между версиями

Версия 12:55, 4 августа 2008

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

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

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

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

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

Реализация на 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

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]

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

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

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

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

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

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

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

Реализация на 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

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 12:34, 17 Oct 2005 (MSD)

  _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;
      },{})