По сравнению с основным алгоритмом имеются некоторые улучшения:

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

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

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

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

Функция qsort

// Коды для стандартной реализации быстрого поиска

#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;

            }

        }

    }

}

В таблице 2.1 приводится время и размер стека, затрачиваемые до и после описанных улучшений.

Таблица 2.1. Влияние улучшений на скорость работы и размер стека

<DIV ALIGN=right></DIV>

Сравнение методов

В данном разделе мы сравним описанные алгоритмы сортировки: вставками, Шелла и быструю сортировку. Есть несколько факторов, влияющих на выбор алгоритма в каждой конкретной ситуации:

Устойчивость. Напомним, что устойчивая сортировка не меняет взаимного расположения элементов с равными ключами. Сортировка вставками - единственный из рассмотренных алгоритмов, обладающих этим свойством.

Память. Сортировке на месте не требуется дополнительная память. Сортировка вставками и Шелла удовлетворяют этому условию. Быстрой сортировке требуется стек для организации рекурсии. Однако, требуемое этому алгоритму место можно сильно уменьшить, повозившись с алгоритмом.

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

Простота. Количество операторов, выполняемых каждым алгоритмом, приведено в таблице 2.2. Более простые алгоритмы вызывают меньше ошибок при программировании.

Таблица 2.2. Сравнение методов сортировки

Таблица 2.3. Время сортировки

<DIV ALIGN=right></DIV>

Дополнительно

Здесь рассмотрим более подробно группу наиболее эффективных методов сортировки. Кроме того в этом разделе мы будем рассматривать программы сортировок в нотации языка Pascal. Методы Шелла и быстрая сортировка здесь будут рассмотрены повторно, но в другой нотации. Итак…

Сортировка включениями

Сортировка включениями с убывающим приращением.

Некоторое усовершенствование сортировки "простыми включениями" было предложено Д.Л.Шеллом в 1959 году. Этот метод мы объясним и продемонстрируем на нашем стандартном примере из 8 элементов.

1   2   3   4   1   2   3   4

                     1   2   1   2   1   2   1   2

     2-сортировка:  44  18  06  42  94  55  12  67

                     1   1   1   1   1   1   1   1

     Результат:     06  12  18  42  44  55  67  94

На первом проходе отдельно группируются и сортируются все элементы, отстоящие друг от друга на четыре позиции. Этот процесс называется 4-сортировкой. В нашем примере из восьми элементов каждая группа содержит ровно два элемента. После этого элементы вновь объединяются в группы с элементами, отстоящими друг от друга на две позиции, и сортируются заново. Этот процесс называется 2-сортировкой. Наконец на третьем проходе все элементы сортируются обычной сортировкой или 1-сортировкой. Сначала может показаться, что необходимость нескольких проходов сортировки, в каждом из которых участвуют все элементы, больше работы потребует, чем сэкономит. Однако на каждом шаге сортировки либо участвует сравнительно мало элементов, либо они уже довольно хорошо упорядочены и требуют относительно мало перестановок. Очевидно, что этот метод  дает упорядоченный массив, и каждый проход будет использовать результаты предыдущего прохода, поскольку каждая i-сортировка объединяет две группы, рассортированные предыдущей 2i-сортировкой. Также ясно, что приемлема любая последовательность приращений, лишь бы последнее было равно 1, так как в худшем случае вся работа будет выполняться на последнем проходе. Однако менее очевидно, что метод убывающего приращения дает лучшие результаты, когда приращения не являются степенями двойки. Таким образом, программа разрабатывается вне связи с конкретной последовательностью приращений. Все t приращений обычно обозначаются через h[1],h[2],...,h[t] с условиями:

h[t] = 1    h[i+1] < h[i]

Каждая h-сортировка  программируется как сортировка простыми включениями, при этом, для того чтобы условие поиска места включения было простым, используется барьер. Ясно, что каждая h-сортировка требует собственного барьера, и что программа должна определять его место как можно проще. Поэтому массив нужно дополнить не одной компонентой A[0], а h[1] компонентами, так, что теперь он описывается как:

A: array [-h[1] .. n] of item;

Этот алгоритм представлен ниже в виде процедуры, названной ShellSort для t=4.

Реализация

              procedure ShellSort;

                 const t=4;

                 var i,j,k,s: index; x: item; m: 1..t;

                    h: array[1..t] of integer;

              begin h[1]:=9; h[2]:= 5; h[3]:=3; h[4]:=1;

                 for m:=1 to t do

                 begin k:=h[m]; s:=-k; {место барьера}

                    for i:= k+1 to n do

                    begin x:=A[i]; j:=i-k;

                      if s=0 then s:=-k; s:=s+1; A[s]:=x;

                      while (x.key < A[j].key) do

                      begin A[j+k]:=A[j]; j:=j-k;

                      end;

                      A[j+k]:=x;

                    end;

                 end;

              end;