====================================================================
> 8. Описание и исходник QuickSort (быстрая сортировка)
====================================================================

                             Основной алгоритм

               Выберем случайным образом какой-то элемент х и
          просмотрим массив, двигаясь слева направо, пока не
          найдем аi больший x, а затем справа налево, пока не
          найдем аi меньший х. Поменяем их местами и продолжим
          процесс просмотра с обменом, пока просмотры не
          встретятся где-то в середине массива. 

               В результате массив разделится на две части:
          левую - с ключами, меньшими х и правую - с ключами,
          большими х.

              Этот шаг называется разделением. Х - центром.
               
              К получившимся частям рекурсивно применяем ту же
          процедуру. В результате получается очень эффективная сортировка.
	  Среднее быстродействие O(nlogn), но возможен случай таких
	  входных данных, на которых алгоритм будет работать за O(n^2)
	  операций. Hа случайных входных данных вероятность
	  такого чрезвычайно мала, кроме того, с этим можно бороться
	  при помощи некоторой модификации метода, описанной ниже.  
	      
	      Устойчивости нет. Поведение неестественно.

 Пример рекурсивной QuickSort
-------------------------------------------------
typedef int item;       /* Тип сортируемых элементов */
typedef int tblIndex;   /* Тип ключей, по которым сортируем */

#define CompGT(a,b) (a > b)

tblIndex partition(T *a, tblIndex lb, tblIndex ub) {
     item t, pivot;
    tblIndex i, j, p;

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

    /* Выбираем центр - pivot */
    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;
        }
    }
}
                                 Улучшения

               Hа практике для увеличения быстроты, 
          можно произвести несколько улучшений:

               1. Произвести случайную перестановку всех чисел
          массива перед сортировкой. Алгоритм с этим улушением 
          называется Randomized Quicksort и работает в среднем за O(nlogn) 
          времени при любых неприятных закономерностях в потоке входных 
          данных. 
           В зависимости от приложения можно использовать 
          этот вариант, либо каждый раз выбирать в качестве центрального 
          для функции partition средний из первого, последнего и среднего
          элементов. 
	   Если же вероятность таких неблагоприятных входных
          данных крайне мала(массив случаен), то этот пункт можно
          вовсе опустить.

               2. Для коротких массивов вызывается сортировка
          вставками. Из-за рекурсии и других "накладных
          расходов" Quicksort оказывается не столь уж
          быстрой для коротких массивов. Поэтому, если в массиве
          меньше 12 элементов, вызывается сортировка вставками.
          Пороговое значение не критично - оно сильно зависит от
          качества генерируемого кода.

               3. Если последний оператор функции является
          вызовом этой функции, говорят о хвостовой рекурсии. Ее
          имеет смысл заменять на итерации - в этом случае лучше
          используется стек.

               4. После разбиения сначала сортируется меньший
          раздел. Это также приводит к лучшему использованию
          стека, поскольку короткие разделы сортируются быстрее
          и им нужен более короткий стек. Требования к памяти
          уменьшаются с n до log n.

          Пример, входящий в стандартную реализацию Си
          использует многие из этих улучшений.

Стандартная реализация итерационной QuickSort
------------------------------------------------

#include <limits.h>
#define MAXSTACK (sizeof(size_t) * CHAR_BIT)

static void exchange(void *a, void *b, size_t size) {
    size_t i;

    /******************
     *  обменять a,b  *
     ******************/

    for (i = sizeof(int); i <= size; i += sizeof(int)) {
        int t = *((int *)a);
        *(((int *)a)++) = *((int *)b);
        *(((int *)b)++) = t;
    }
    for (i = i - sizeof(int) + 1; i <= size; i++) {
        char t = *((char *)a);
        *(((char *)a)++) = *((char *)b);
        *(((char *)b)++) = t;
    }
}

void qsort(void *base, size_t nmemb, size_t size,
        int (*compar)(const void *, const void *)) {
    void *lbStack[MAXSTACK], *ubStack[MAXSTACK];
    int sp;
    unsigned int offset;

    lbStack[0] = (char *)base;
    ubStack[0] = (char *)base + (nmemb-1)*size;
    for (sp = 0; sp >= 0; sp--) {
        char *lb, *ub, *m;
        char *P, *i, *j;

        lb = lbStack[sp];
        ub = ubStack[sp];

        while (lb < ub) {

            /* выбираем центр и меняемся с 1м элементом */
            offset = (ub - lb) >> 1;
            P = lb + offset - offset % size;
            exchange (lb, P, size);

            /* разделение в два сегмента */
            i = lb + size;
            j = ub;
            while (1) {
                while (i < j && compar(lb, i) > 0) i += size;
                while (j >= i && compar(j, lb) > 0) j -= size;
                if (i >= j) break;
                exchange (i, j, size);
                j -= size;
                i += size;
            }

            /* центр в A[j] */
            exchange (lb, j, size);
            m = j;

            /* Меньший сегмент продолжаем обрабатывать, больший - в стек */
            if (m - lb <= ub - m) {
                if (m + size < ub) {
                    lbStack[sp] = m + size;
                    ubStack[sp++] = ub;
                }
                ub = m - size;
            } else {
                if (m - size > lb) {
                    lbStack[sp] = lb; 
                    ubStack[sp++] = m - size;
                }
                lb = m + size;
            }
        }
    }
}