C++ [C] Сортировка Хоара

[Mathian]

"Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.
Псевдокод:

quickSort ( массив a, верхняя граница N ) 
{
    Выбрать опорный элемент p - середину массива
    Разделить массив по этому элементу
    Если подмассив слева от p содержит более одного элемента,
    вызвать quickSort для него.
    Если подмассив справа от p содержит более одного элемента,
    вызвать quickSort для него.
}

Реализация:

template<class T>
void quickSortR(T* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.
 
    long i = 0, j = N;      // поставить указатели на исходные места
    T temp, p;
 
    p = a[ N>>1 ];      // центральный элемент
 
    // процедура разделения
    do {
        while ( a[i] < p ) i++;
        while ( a[j] > p ) j--;
 
        if (i <= j) {
            temp = a[i]; a[i] = a[j]; a[j] = temp;
            i++; j--;
        }
    } while ( i<=j );
 
    // рекурсивные вызовы, если есть, что сортировать 
    if ( j > 0 ) quickSortR(a, j);
    if ( N > i ) quickSortR(a+i, N-i);
}

Каждое разделение требует, очевидно, O операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике.

Итеративный алгоритм быстрой сортировки:
Псевдокод:

Итеративная QuickSort (массив a, размер size) {
    Положить в стек запрос на сортировку массива от 0 до size-1.
    do {
        Взять границы lb и ub текущего массива из стека.
        do {
            1. Произвести операцию разделения над текущим массивом a[lb..ub].
            2. Отправить границы большей из получившихся частей в стек.
            3. Передвинуть границы ub, lb чтобы они указывали на меньшую часть.
        } пока меньшая часть состоит из двух или более элементов
    } пока в стеке есть запросы
}

Реализация:

#define MAXSTACK 2048 // максимальный размер стека
template<class T>
void qSortI(T a[], long size) {
 
    long i, j; // указатели, участвующие в разделении
    long lb, ub; // границы сортируемого в цикле фрагмента
 
    long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
    // каждый запрос задается парой значений,
    // а именно: левой(lbstack) и правой(ubstack)
    // границами промежутка
    long stackpos = 1; // текущая позиция стека
    long ppos; // середина массива
    T pivot; // опорный элемент
    T temp;
 
    lbstack[1] = 0;
    ubstack[1] = size-1;
 
    do {
        // Взять границы lb и ub текущего массива из стека.
        lb = lbstack[ stackpos ];
        ub = ubstack[ stackpos ];
        stackpos--;
 
        do {
            // Шаг 1. Разделение по элементу pivot
            ppos = ( lb + ub ) >> 1;
            i = lb; j = ub; pivot = a[ppos];
            do {
                while ( a[i] < pivot ) i++;
                while ( pivot < a[j] ) j--;
                if ( i <= j ) {
                    temp = a[i]; a[i] = a[j]; a[j] = temp;
                    i++; j--;
                }
            } while ( i <= j );
 
            // Сейчас указатель i указывает на начало правого подмассива,
            // j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.
            // Возможен случай, когда указатель i или j выходит за границу массива
 
            // Шаги 2, 3. Отправляем большую часть в стек и двигаем lb,ub
            if ( i < ppos ) { // правая часть больше
                if ( i < ub ) { // если в ней больше 1 элемента - нужно
                    stackpos++; // сортировать, запрос в стек
                    lbstack[ stackpos ] = i;
                    ubstack[ stackpos ] = ub;
                }
            ub = j; // следующая итерация разделения
            // будет работать с левой частью
            } else { // левая часть больше
                if ( j > lb ) {
                    stackpos++;
                    lbstack[ stackpos ] = lb;
                    ubstack[ stackpos ] = j;
                }
                lb = i;
            }
        } while ( lb < ub ); // пока в меньшей части более 1 элемента
    } while ( stackpos != 0 ); // пока есть запросы в стеке
}

Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.

Автор: Неизвестно