Delphi World - Описание и исходник быстрой сортировки
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Описание и исходник быстрой сортировки

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

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


Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования