Лекция 4

int function Partition (Array A, int Lb, int Ub);   begin   Выбрать центральный среди элементов A[Lb]...A[Ub];   Переупорядочить A[Lb]...A[Ub] так чтобы:          слева  от центра все значения были <= центрального          справа от центра все значения были >= центрального   Вернуть индекс центрального элемента;   end;   procedure QuickSort (Array A, int Lb, int Ub);   begin   if Lb < Ub then     M = Partition (A, Lb, Ub);     QuickSort (A, Lb, M - 1);     QuickSort (A, M + 1, Ub);   end;

Рис 2-4. Пример работы алгоритма Quicksort

В процессе сортировки может потребоваться передвинуть центральный элемент. Если нам повезет, выбранный элемент окажется медианой значений массива, т.е. разделит его пополам. Предположим на минутку, что это и в самом деле так. Поскольку на каждом шаге мы делим массив пополам, а функция Partition в конце концов просмотрит все n элементов, время работы алгоритма есть O(n lg n).

В качестве центрального функция Partition может попросту брать первый элемент (A[Lb]). Все остальные элементы массива мы сравниваем с центральным и передвигаем либо влево от него, либо вправо. Есть, однако, один случай, который безжалостно разрушает эту прекрасную простоту. Предположим, что наш массив с самого начала отсортирован. Функция Partition всегда будет получать в качестве центрального минимальный элемент и потому разделит массив наихудшим способом: в левом разделе окажется один элемент, соответственно, в правом останется Ub - Lb элементов. Таким образом, каждый рекурсивный вызов процедуры QuickSort всего лишь уменьшит длину сортируемого массива на 1. В результате для выполнения сортировки понадобится n рекурсивных вызовов, что приводит к времени работы алгоритма порядка O(n²). Один из способов побороть эту проблему - случайно выбирать центральный элемент. Это сделает наихудший случай чрезвычайно маловероятным.

Реализация

В приведенной реализации

 

typedef int T;          /* Тип элемента, который нужно сортировать */

typedef int tblIndex;   /* Тип ключа сортировки */

 

#define сompGT(a,b) (a > b)

 

tblIndex partition(T *a, tblIndex lb, tblIndex ub) {

    T t, pivot;

    tblIndex i, j, p;

 

   /**********************************

    *  разделение массива a[lb..ub]  *

    **********************************/

 

    /* выбор центрального элемента и обмен его с первым */

    p = lb + ((ub - lb)>>1);

    pivot = a[p];

    a[p] = a[lb];

 

    /* сортировка lb+1..ub относительно центрального элемента */

    i = lb+1;

    j = ub;

    while (1) {

        while (i < j && compGT(pivot, a[i])) i++;

        while (j >= i && compGT(a[j], pivot)) j--;

        if (i >= j) break;

        t = a[i];

        a[i] = a[j];

        a[j] = t;

        j--; i++;

    }

 

    /* центральный элемент размещается в a[j] */

    a[lb] = a[j];

    a[j] = pivot;

 

    return j;

}

 

void quickSort(T *a, tblIndex lb, tblIndex ub) {

    tblIndex m;

 

   /**********************************

    *  сортировка массива a[lb..ub]  *

    **********************************/

 

    while (lb < ub) {

 

        /* короткие массивы сортируются методом вставки */

        if (ub - lb <= 12) {

            insertSort(a, lb, ub);

            return;

        }

 

        /* разделение на два сегмента */

        m = partition (a, lb, ub);

 

        /* сортировка меньшего раздела */

        /* требуется более короткий стек */

        if (m - lb <= ub - m) {

            quickSort(a, lb, m - 1);

            lb = m + 1;

        } else {

            quickSort(a, m + 1, ub);

            ub = m - 1;

        }

    }

}