Для формирования новой очереди Q

Сортировка Шелла

Метод, предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой по месту. Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места. Среднее время для сортировки Шелла равняется O(n^1.25), для худшего случая оценкой является O(n^1.5). Дальнейшие свойства см. в книге Кнута [1998] [Knuth].

Теория

На рис. 2.2(a) был приведен пример сортировки вставками. Мы сначала вынимали 1, затем сдвигали 3 и 5 на одну позицию вниз, после чего вставляли 1. Таким образом, нам требовались два сдвига. В следующий раз нам требовалось еще два сдвига, чтобы вставить на нужное место 2. На весь процесс нам требовалось 2 + 2 + 1 = 5 сдвигов.

На рис. 2.2(b) иллюстрируется сортировка Шелла. Мы начинаем, производя сортировку вставками с шагом 2. Сначала мы рассматриваем числа 3 и 1: извлекаем 2, сдвигаем 3 на 1 позицию с шагом 2, вставляем 2. Затем повторяем то же для чисел 5 и 2: извлекаем 2, сдвигаем вниз 5, вставляем 2. И т.д. Закончив сортировку с шагом 2, производим ее с шагом 1, т.е. выполняем обычную сортировку вставками. Всего при этом нам понадобится 1 + 1 + 1 = 3 сдвига. Таким образом, использовав вначале шаг, больший 1, мы добились меньшего числа сдвигов.

Рис. 2-2. Сортировка Шелла

Можно использовать самые разные схемы выбора шагов. Как правило, сначала мы сортируем массив с большим шагом, затем уменьшаем шаг и повторяем сортировку. В самом конце сортируем с шагом 1. Хотя этот метод легко объяснить, его формальный анализ довольно труден. В частности, теоретикам не удалось найти оптимальную схему выбора шагов. Кнут [Knuth] провел множество экспериментов и нашел следующую формулу выбора шагов h для массива длины N:

в последовательности h₁ = 1, h_s+1 = 3h_s + 1, ... взять h_t, если h_t+2 >= N.

Вот несколько первых значений h:

h₁ = 1
h₂ = (3 x 1) + 1 = 4
h₃ = (3 x 4) + 1 = 13
h₄ = (3 x 13) + 1 = 40
h₅ = (3 x 40) + 1 = 121

Чтобы отсортировать массив длиной 100, прежде всего найдем номер s, для которого h_s >= 100. Согласно приведенным цифрам, s = 5. Нужное нам значение находится двумя строчками выше. Таким образом, последовательность шагов при сортировке будет такой: 13-4-1. Ну, конечно, нам не нужно хранить эту последовательность: очередное значение h находится из предыдущего по формуле

h_s-1 = [h_s / 3].

Реализация

В реализации сортировки Шелла на Си следует изменить операторы typedef T и сравнения compGT так, чтобы они соответствовали данным, хранимым в массиве. Основная часть алгоритма - сортировка вставками с шагом h.

// Коды для сортировки Шелла

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

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

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

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

tblIndex n, h, i, j;

T t;

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

* сортируемый массив a[lb..ub] *

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

/* Вычисление наибольшего шага */

n = ub - lb + 1;

h = 1;

if (n < 14)

h = 1;

else if (sizeof(tblIndex) == 2 && n > 29524)

h = 3280;

else {

while (h < n) h = 3*h + 1;

h /= 3;

h /= 3;

}

while (h > 0) {

/* «Сортировка вставкой» с шагом h */

for (i = lb + h; i <= ub; i++) {

t = a[i];

for (j = i-h; j >= lb && compGT(a[j], t); j -= h)

a[j+h] = a[j];

a[j+h] = t;

}

/* Вычисление следующего шага */

h /= 3;

}

}

Быстрая сортировка

Хотя идея Шелла значительно улучшает сортировку вставками, резервы еще остаются. Один из наиболее известных алгоритмов сортировки - быстрая сортировка, предложенная Ч.Хоором. Метод и в самом деле очень быстр, недаром по-английски его так и величают QuickSort к неудовольствию всех «спелл-чекеров».

Этому методу требуется O(n lg n) в среднем и O(n²) в худшем случае. К счастью, если принять адекватные предосторожности, наихудший случай крайне маловероятен. Быстрый поиск не является устойчивым. Кроме того, ему требуется стек, т.е. он не является и методом сортировки на месте. Дальнейшую информацию можно получить в работе Кормена [1990] [Cormen].

Теория

Алгоритм разбивает сортируемый массив на разделы, затем рекурсивно сортирует каждый раздел. В функции Partition (рис. 2.3) один из элементов массива выбирается в качестве центрального. Ключи, меньшие центрального следует расположить слева от него, те, которые больше, - справа.

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.3. Быстрый поиск

На рис. 2.4(a) в качестве центрального (pivot) выбран элемент 3. Индексы начинают изменяться с концов массива. Индекс i начинается слева и используется для выбора элементов, которые больше центрального, индекс j начинается справа и используется для выбора элементов, которые меньше центрального. Эти элементы меняются местами - см. рис. 2.4(b). Процедура QuickSort рекурсивно сортирует два подмассива, в результате получается массив, представленный на рис. 2.4(c).

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

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

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

Реализация

В приведенной реализации алгоритма на Си операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в массиве.

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;

}

}

}

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

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

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

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

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

Функция qsort из стандартной библиотеки Си основана на алгоритме 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;

}

}

}

}

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

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

кол-во элементов	время (µs)	размер стека
до	после	до	после
	1,630
4,096	34,183	20,016	1,908
65,536	658,003	460,737	2,436

<DIV ALIGN=right></DIV>

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

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

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

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

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

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

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

метод	кол-во операторов	ср. время	время для наихудшего случая
	сортировка вставками		O(n2)	O(n2)
	сортировка Шелла		O(n1.25)	O(n1.5)
	быстрая сортировка		O(n lg n)	O(n2)

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

кол-во элементов	вставки	Шелл	quicksort
	39 µs	45 µs	51 µs
	4,969 µs	1,230 µs	911 µs
4,096	1.315 sec	.033 sec	.020 sec
65,536	416.437 sec	1.254 sec	.461 sec

<DIV ALIGN=right></DIV>

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

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

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

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

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

1 2 3 4 1 2 3 4

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

1 2 1 2 1 2 1 2

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

1 1 1 1 1 1 1 1

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

Результат: 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;

Сортировка выбором

Турнирная сортировка

Идея выбора может привести к эффективному алгоритму сортировки. Весь вопрос в том, чтобы найти более эффективный метод определения i-го наибольшего имени, чего можно добиться, используя механизм турнира с выбыванием. Суть его такова: сравниваются x₁:x₂,x₃:x₄,…,x_n-1:x_n,затем сравниваются “победители” (т.е., большие имена) этих сравнений и т.д. Эта процедура для n=8 показана на рисунке:

94

55 94

55 42 94 67

44 55 12 42 94 18 06 67

Заметим, что для определения наибольшего имени этот процесс требует n-1 сравнений ; но определив наибольшее имя, мы обладаем большим объемом информации о втором по величине (в порядке убывания) имени: оно должно быть одним из тех, которые “потерпели поражение” от наибольшего имени. Таким образом второе по величине имя теперь можно определить, заменяя наибольшее имя на -¥ и вновь осуществляя сравнение вдоль пути от наибольшего имени к корню.

Реализация

procedure turnir_sort;

Const MAX_VALUE=-32767;

Type

index1 = 1 .. 2*n-1;

item1 = record

key: integer; { ключ сортировки }

adres: index; { описание других компонент }

end;

var i,j,j1:index1;

B:array [index1] of item1;

begin

for i:=n to 2*n-1 do

begin

B[i].key:=A[i-n+1].key;

B[i].adres:=i;

end;

i:=2*n-1;j:=1;

repeat {первый круг}

if B[i].key>B[i-1].key then j:=i else j:=i-1;

B[j div 2].key:=B[j].key;

B[j div 2].adres:=B[j].adres;

i:=i-2;

until(i<3);

A[1].key:=B[1].key;

j1:=2;

repeat {последующие круги}

if ((B[1].adres mod 2)=0) then i:=B[1].adres+1

else i:=B[1].adres;

B[B[1].adres].key:=MAX_VALUE;

repeat

if B[i].key>B[i-1].key then j:=i else j:=i-1;

B[j div 2].key:=B[j].key;

B[j div 2].adres:=B[j].adres;

i:=i div 2;

if ((i mod 2)=0) then i:=i+1;

until(i<3);

A[j1].key:=B[1].key;

j1:=j1+1;

until(j1>n);

end;

Пирамидальная сортировка

Идея турнира с выбыванием прослеживается при сортировке весьма отчетливо, если имена образуют пирамиду. Пирамида-это полностью сбалансированное бинарное дерево высоты h, в котором все листья находятся на расстоянии h или h-1 от корня и все потомки узла меньше его самого; кроме того, в нем все листья уровня h максимально смещены влево.(см. рис.)

94

67 18

44 55 12 06

Чтобы получить удобное линейное представление дерева, пирамиду можно хранить по уровням в одномерном массиве: сыновья имени из i-й позиции есть имена в позициях 2i и 2i+1. Таким образом, пирамида, представленная на рисунке, принимает вид:

I: 1 2 3 4 5 6 7 8

x_i: 94 67 18 44 55 12 06 42

Заметим, что в пирамиде наибольшее имя должно находиться в корне и, таким образом, всегда в первой позиции массива, представляющего пирамиду. Обмен местами первого имени с n-м помещает наибольшее имя в его правильную позицию, но нарушает свойство пирамидальности в первых n-1 именах. Если мы можем сначала построить пирамиду, а затем восстанавливать ее эффективно, то всё в порядке, так как тогда можно производить сортировку следующим образом:

Построить пирамиду из x_1,…,x_n,

Поменять местами x₁ и x_i

For i:=n downto 2 do Восстановить пирамиду

в x₁,…,x_i-1

Это общее описание пирамидальной сортировки.

Как преобразовать в пирамиду данное бинарное дерево, все листья которого максимально сдвинуты влево и оба поддерева которого являются пирамидами? Сравниваем корень с большим из сыновей. Если корень больше, дерево уже является пирамидой; в противном случае мы меняем его местами с большим сыном и применяем рекурсивно алгоритм восстановления к поддереву, корень которого заменялся. Таким образом, процедура RESTORE(j,k)восстановления пирамиды из последовательности xj,xj+1,…,xk в предположении, что все поддеревья суть пирамиды, такова:

procedure RESTORE(j,k)

пусть x_m есть больший из сыновей x_j

if x_j ¹ лист then поменять местами x_m и x_j

if x_m>x_j then

RESTORE(m,k)

Переписывая это итеративным способом и дополняя деталями, мы получаем следующий алгоритм.

Реализация

procedure RESTORE(var f,l:index);

var j,m:index; x:item;

begin

j:=f;

while(j<=(l div 2)) do

begin

if (2*j<l) and (A[2*j].key<A[2*j+1].key) then m:=2*j+1 else m:=2*j;

if (A[m].key>A[j].key) then

begin

x:=A[m]; A[m]:=A[j]; A[j]:=x;

j:=m;

end

else j:=l;

end;

end;

Для построения пирамиды вначале заметим, что свойство пирамидальности уже выполняется (тривиально) для каждого листа (x_i, i=ë0.5nû+1,…,n) и что обращение к RESTORE(i,n)для i=ë0.5nû, ë0.5nû-1,…,1 преобразует таблицу в пирамиду на всех высших уровнях. Таким образом, пирамидальная сортировка производится так, как показано в алгоритме. Первый цикл for строит пирамиду и известен как фаза построения; второй цикл for носит название фазы выбора.

Реализация

procedure piramid_sort;

var i,nn,o,o1:index; x:item;

begin

nn:=n; o:=1;

for i:=(nn div 2) downto 1 do RESTORE(i,nn);

for i:=nn downto 2 do

begin

x:=A[1];

A[1]:=A[i];

A[i]:=x;

o1:=i-1;

RESTORE(o,o1);

end;

end;

Сортировка обменом

Сортировка разделением

Рассмотрим еще один метод сортировки обменом. Он обладает столь блестящими характеристиками, что его изобретатель К.Хоор окрестил его быстрой сортировкой. Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях. Предположим, что нам даны n элементов с ключами, расположенными в обратном порядке. Их можно рассортировать, выполнив всего n/2 обменов, если сначала поменять местами самый левый и самый правый элементы и так постепенно продвигаться от двух концов к середине. Разумеется, это возможно, но только если мы твердо знаем, что элементы расположены строго в обратном порядке.

Попробуем рассмотреть следующий алгоритм: выберем случайным образом какой-то элемент (назовем его х), просмотрим массив, двигаясь справа налево, пока не найдем элемента A[i] > х, а затем просмотрим его справа налево, пока не обнаружим A[i]<х. Теперь поменяем местами эти два элемента и продолжим процесс "просмотра с обменом", пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую – с ключами меньшими, чем х и правую - с ключами большими. Теперь запишем этот алгоритм разделения в виде процедуры в программе (см. ниже). Заметим что отношения > и < заменены на «больше или равно» и «меньше или равно», отрицания которых в операторе цикла с предусловием - это < и >. При такой замене х действует как барьер для обоих просмотров.

Реализация

procedure partition;

var w,x: item;

begin i:=1; j:=n;

"выбор случайного элемента х;"

repeat

while (A[i].key < x.key) do i:=i+1;

while (x.key < A[j].key) do j:=j-1;

if (i<=j) then

begin w:=A[i]; A[i]:=A[j]; A[j]:=w;

i:=i+1; j:=j-1;

end;

until (i>j);

end;

Если, например, в качестве х выбрать средний ключ, равный 42, из массива ключей 44 55 12 |42| 94 06 18 67 то, для того, чтобы разделить массив, потребуется два обмена

18 06 12 |42| 94 55 44 67

конечные значения индексов i=5 и j=3. Ключи A[1],...,A[i-1] меньше или равны ключу х=42, ключи A[j+1],...,A[n] больше или равны х. Следовательно, мы получили два подмассива:

A[k].key <= x.key для k=1, ..., i-1,

A[k].key >= x.key для k=j+1, ..., n

и, следовательно

A[k].key = x.key для k=j+1, ..., i-1

Этот алгоритм очень прост и эффективен. Но он так же может быть весьма неуклюжим, как видно из примера с n одинаковыми ключами, в котором выполняется n/2 обменов. Эти ненужные обмены можно легко устранить, заменив, операторы просмотра на

while (A[i].key < x.key) do i:=i+1;

while (x.key < A[j].key) do j:=j-1;

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

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

Реализация

procedure QuickSort;

procedure sort (l,r: index);

var i,j: index; w,x: item;

begin i:=l; j:=r;

x:= A[(l+r) div 2];

repeat

while (A[i].key < x.key) do i:=i+1;

while (x.key < A[j].key) do j:=j-1;

if (i<=j) then

begin w:=A[i]; A[i]:=A[j]; A[j]:= w;

i:=i+1; j:=j-1;

end;

until (i>j);

if (l<j) then sort(l,j);

if (i<r) then sort(i,r)

end;

begin sort(1,n);

end; { QuickSort }

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

Основа итеративного решения - введение списка вопросов на разделения, которые еще предстоит выполнить. После каждого шага нужно произвести два очередных разделения, и лишь одно из них можно выполнить непосредственно при следующей итерации, запрос на другое заносится в список. Важно, разумеется, что вопросы из списка выполняются в обратном порядке. Это предполагает, что первый занесенный в список запрос выполняется последним и наоборот; список ведет себя как пульсирующий стек. В следующей не рекурсивной версии быстрой сортировки каждый запрос представлен просто левым и правыми индексами, определяющими границы части, которую впоследствии нужно будет разделить. Итак, мы вводим переменную - массив, называемую stack, и индекс s, указывающий на самую последнюю запись в этом стеке. Вопрос о размере стека m требует более детального анализа алгоритма.

Реализация

procedure QuickSort1;

const m = 12;

var i,j,l,r: index;

x,w: item;

s: 0..m;

stack: array[1..m] of

record l,r: index end;

begin s:= 1; stack[1].l:=1; stack[1].r:=n;

repeat {выбор запроса из вершины стека}

l:=stack[s].l; r:=stack[s].r; s:=s-1;

repeat { разделить A[l] ... A[r] }

i:=l; j:=r; x:=A[(l+r) div2];

repeat

while (A[i].key < x.key) do i:=i+1;

while (x.key < A[j].key) do j:=j-1;

if (i<=j) then

begin w:=A[i]; A[i]:=A[j]; A[j]:=w;

i:= i+1; j:=j-1;

end;

until (i>j);

if (i<r) then

begin { запись в стек запроса на сортировку правой части }

s:=s+1; stack[s].l:=i; stack[s].r:=r;

end;

r:=j;

until (l>=r);

until (s=0);

end; { QuickSort1 }

Словари

Словари - это структуры данных, которые поддерживают операции поиска, вставки и удаления. Один из наиболее эффективных способов реализации словаря - хеш-таблицы. Как правило, к ключам применяется какая-нибудь простая функция, значения которой дают место ключа в словаре; хорошая функция рандомизирует значения ключей, рассеивая их по интервалу [1, N], где N - количество мест в словаре (объем хеш-таблицы). Мы рассмотрим также двоичные и красно-черные деревья. Методы работы с обоими типами деревьев включают приемы, с которыми мы познакомились при изучении бинарного поиска. Наконец, слоёные списки (skip lists) - еще одна иллюстрация пользы применения случайных чисел при построении словарей.

Хеш-таблицы

Один из наиболее эффективных способов реализации словаря - хеш-таблица. Среднее время поиска элемента в ней есть O(1), время для наихудшего случая - O(n). Прекрасное изложение хеширования можно найти в работах Кормена [1990] [Cormen] и Кнута [1998] [Knuth]. Чтобы читать статьи на эту тему, вам понадобится владеть соответствующей терминологией. Здесь описан метод, известный как связывание или открытое хеширование [Aho]. Другой метод, известный как замкнутое хеширование [Aho] или закрытая адресация [Knuth], здесь не обсуждаются. Ну, как?

Теория

Хеш-таблица - это обычный массив с необычной адресацией, задаваемой хеш-функцией. Например, на рис. 3.1 hashTable - это массив из 8 элементов. Каждый элемент представляет собой указатель на линейный список, хранящий числа. Хеш-функция в этом примере просто делит ключ на 8 и использует остаток как индекс в таблице. Это дает нам числа от 0 до 7 Поскольку для адресации в hashTable нам и нужны числа от 0 до 7, алгоритм гарантирует допустимые значения индексов.

Рис. 3.1. Хеш-таблица

Чтобы вставить в таблицу новый элемент, мы хешируем ключ. Этим мы определяем список, в который его нужно добавить. Затем вставляем элемент в начало этого списка. Например, чтобы добавить 11, мы делим 11 на 8 и получаем остаток 3. Таким образом, 11 следует разместить в списке, на начало которого указывает hashTable[3]. Чтобы найти число, мы его хешируем и проходим по соответствующему списку. Чтобы удалить число, мы находим его и удаляем элемент списка, его содержащий.

При добавлении элементов в хеш-таблицу выделяются куски динамической памяти, которые организуются в виде связанных списков, каждый из которых соответствует входу хеш-таблицы. Этот метод называется связыванием. Другой метод, в котором все элементы располагаются в самой хеш-таблице, известен как прямая или открытая адресация; его описание вы найдете в цитируемой литературе.

Если хеш-функция распределяет совокупность возможных ключей равномерно по множеству индексов, то хеширование эффективно разбивает множество ключей. Наихудший случай - когда все ключи хешируются в один индекс. При этом мы работаем с одним линейным списком, который и вынуждены последовательно сканировать каждый раз, когда что-нибудь делаем. Отсюда видно, как важна хорошая хеш-функция. Здесь мы рассмотрим лишь несколько из возможных подходов. При иллюстрации методов предполагается, что unsigned char располагается в 8 битах, unsigned short int - в 16, unsigned long int - в 32.

Деление (размер таблицы hashTableSize - простое число). Этот метод использован в последнем примере. Хеширующее значение hashValue, изменяющееся от 0 до (hashTableSize - 1), равно остатку от деления ключа на размер хеш-таблицы. Вот как это может выглядеть:

typedef int HashIndexType;

HashIndexType Hash(int Key) {

return Key % HashTableSize;

}

Для успеха этого метода очень важен выбор подходящего значения hashTableSize. Если, например, hashTableSize равняется двум, то для четных ключей хеш-значения будут четными, для нечетных - нечетными. Ясно, что это нежелательно - ведь если все ключи окажутся четными, они попадут в один элемент таблицы. Аналогично, если все ключи окажутся четными, то hashTableSize, равное степени двух, попросту возьмет часть битов Key в качестве индекса. Чтобы получить более случайное распределение ключей, в качестве hashTableSize нужно брать простое число, не слишком близкое к степени двух.

Мультипликативный метод (размер таблицы hashTableSize есть степень 2ⁿ). Значение key умножается на константу, затем от результата берется необходимое число битов. В качестве такой константы Кнут рекомендует золотое сечение (sqrt(5) - 1)/2 = 0.6180339887499. Пусть, например, мы работаем с байтами. Умножив золотое сечение на 28, получаем 158. Перемножим 8-битовый ключ и 158, получаем 16-битовое целое. Для таблицы длиной 25 в качестве хеширующего значения берем 5 младших битов младшего слова, содержащего такое произведение. Вот как можно реализовать этот метод:

/* 8-bit index */

typedef unsigned char HashIndexType;

static const HashIndexType K = 158;

/* 16-bit index */

typedef unsigned short int HashIndexType;

static const HashIndexType K = 40503;

/* 32-bit index */

typedef unsigned long int HashIndexType;

static const HashIndexType K = 2654435769;

/* w=bitwidth(HashIndexType), size of table=2**m */

static const int S = w - m;

HashIndexType HashValue = (HashIndexType)(K * Key) S;

Пусть, например, размер таблицы hashTableSize равен 1024 (2¹⁰). Тогда нам достаточен 16-битный индекс и S будет присвоено значение 16 - 10 = 6. В итоге получаем:

typedef unsigned short int HashIndexType;

HashIndexType Hash(int Key) {

static const HashIndexType K = 40503;

static const int S = 6;

return (HashIndexType)(K * Key) S;

}

Аддитивный метод для строк переменной длины (размер таблицы равен 256). Для строк переменной длины вполне разумные результаты дает сложение по модулю 256. В этом случае результат hashValue заключен между 0 и 255.

typedef unsigned char HashIndexType;

HashIndexType Hash(char *str) {

HashIndexType h = 0;

while (*str) h += *str++;

return h;

}

Исключающее ИЛИ для строк переменной длины (размер таблицы равен 256). Этот метод аналогичен аддитивному, но успешно различает схожие слова и анаграммы (аддитивный метод даст одно значение для XY и YX). Метод, как легко догадаться, заключается в том, что к элементам строки последовательно применяется операция "исключающее или". В нижеследующем алгоритме добавляется случайная компонента, чтобы еще улучшить результат.

typedef unsigned char HashIndexType;

unsigned char Rand8[256];

HashIndexType Hash(char *str) {

unsigned char h = 0;

while (*str) h = Rand8[h ^ *str++];

return h;

}

Здесь Rand8 - таблица из 256 восьмибитовых случайных чисел. Их точный порядок не критичен. Корни этого метода лежат в криптографии; он оказался вполне эффективным (Pearson [1990]).

Исключающее ИЛИ для строк переменной длины (размер таблицы <= 65536). Если мы хешируем строку дважды, мы получим хеш-значение для таблицы любой длины до 65536. Когда строка хешируется во второй раз, к первому символу прибавляется 1. Получаемые два 8-битовых числа объединяются в одно 16-битовое.

typedef unsigned short int HashIndexType;

unsigned char Rand8[256];

HashIndexType Hash(char *str) {

HashIndexType h;

unsigned char h1, h2;

if (*str == 0) return 0;

h1 = *str; h2 = *str + 1;

str++;

while (*str) {

h1 = Rand8[h1 ^ *str];

h2 = Rand8[h2 ^ *str];

str++;

}

/* h is in range 0..65535 */

h = ((HashIndexType)h1 << 8)|(HashIndexType)h2;

/* use division method to scale */

Return h % HashTableSize

}

Размер хеш-таблицы должен быть достаточно большим, чтобы в ней оставалось разумно большое число пустых мест. Как видно из таблицы 3.1, чем меньше таблица, тем больше среднее время поиска ключа в ней. Хеш-таблицу можно рассматривать как совокупность связанных списков. По мере того, как таблица растет, увеличивается количество списков и, соответственно, среднее число узлов в каждом списке уменьшается. Пусть количество элементов равно n. Если размер таблицы равен 1, то таблица вырождается в один список длины n. Если размер таблицы равен 2 и хеширование идеально, то нам придется иметь дело с двумя списками по n/100 элементов в каждом. Это сильно уменьшает длину списка, в котором нужно искать. Как мы видим в таблице 3.1, имеется значительная свободы в выборе длины таблицы.

Таблица 3.1. Зависимость среднего времени поиска (µs) от hashTableSize. Сортируются 4096 элементов.

Размер	Время		Размер	Время

Реализация

В реализации алгоритма на Си операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в массиве. Для работы программы следует также определить hashTableSize и отвести место под hashTable. В хеш-функции hash использован метод деления. Функция insertNode отводит память под новый узел и вставляет его в таблицу. Функция deleteNode удаляет узел и освобождает память, где он располагался. Функция findNode ищет в таблице заданный ключ.

// Коды для хеш-таблиц

typedef int T; /* type of item to be sorted */

#define compEQ(a,b) (a == b)

typedef struct Node_ {

struct Node_ *next; /* next node */

T data; /* data stored in node */

} Node;

typedef int hashTableIndex;

Node **hashTable;

int hashTableSize;

hashTableIndex hash(T data) {

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

* hash function applied to data *

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

return (data % hashTableSize);

}

Node *insertNode(T data) {

Node *p, *p0;

hashTableIndex bucket;

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

* allocate node for data and insert in table *

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

/* insert node at beginning of list */

bucket = hash(data);

if ((p = malloc(sizeof(Node))) == 0) {

fprintf (stderr, "out of memory (insertNode)\n");

exit(1);

}

p0 = hashTable[bucket];

hashTable[bucket] = p;

p->next = p0;

p->data = data;

return p;

}

void deleteNode(T data) {

Node *p0, *p;

hashTableIndex bucket;

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

* delete node containing data from table *

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

/* find node */

p0 = 0;

bucket = hash(data);

p = hashTable[bucket];

while (p && !compEQ(p->data, data)) {

p0 = p;

p = p->next;

}

if (!p) return;

/* p designates node to delete, remove it from list */

if (p0)

/* not first node, p0 points to previous node */

p0->next = p->next;

else

/* first node on chain */

hashTable[bucket] = p->next;

free (p);

}

Node *findNode (T data) {

Node *p;

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

* find node containing data *

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

p = hashTable[hash(data)];

while (p && !compEQ(p->data, data))

p = p->next;

return p;

}

Поиск в бинарных деревьях

В разделе 1 мы использовали двоичный поиск для поиска данных в массиве. Этот метод чрезвычайно эффективен, поскольку каждая итерация вдвое уменьшает число элементов, среди которых нам нужно продолжать поиск. Однако, поскольку данные хранятся в массиве, операции вставки и удаления элементов не столь эффективны. Двоичные деревья позволяют сохранить эффективность всех трех операций - если работа идет с "случайными" данными. В этом случае время поиска оценивается как O(lg n). Наихудший случай - когда вставляются упорядоченные данные. В этом случае оценка время поиска - O(n). Подробности вы найдете в работе Кормена [1990] [Cormen].

Теория

Двоичное дерево - это дерево, у которого каждый узел имеет не более двух наследников. Пример бинарного дерева приведен на рис. 3.2. Предполагая, что k содержит значение, хранимое в данном узле, мы можем сказать, что бинарное дерево обладает следующим свойством: у всех узлов, расположенных слева от данного узла, значение соответствующего поля меньше, чем k, у всех узлов, расположенных справа от него, - больше. Вершину дерева называют его корнем, узлы, у которых отсутствуют оба наследника, называются листьями. Корень дерева на рис. 3.2 содержит 20, а листья - 4, 16, 37 и 43. Высота дерева - это длина наидлиннейшего из путей от корня к листьям. В нашем примере высота дерева равна 2.

Рис. 3.2. Двоичное дерево

Чтобы найти в дереве какое-то значение, мы стартуем из корня и движемся вниз. Например, для поиска числа 16, мы замечаем, что 16 < 20, и потому идем влево. При втором сравнении видим, что 16 > 7, и потому мы движемся вправо. Третья попытка успешна - мы находим элемент с ключом, равным 16.

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

Рис. 3.3. Несбалансированное бинарное дерево

Вставка и удаление

Чтобы лучше понять, как дерево становится несбалансированным, посмотрим на процесс вставки пристальнее. Чтобы вставить 18 в дерево на рис. 3.2 мы сначала должны найти это число. Поиск приводит нас в узел 16, где благополучно завершается. Поскольку 18 16, мы попросту добавляет узел 18 в качестве правого потомка узла 16 (рис. 3.4).

На этом примере хорошо видно, как возникает несбалансированность дерева. Если данные поступают в возрастающем порядке, каждый новый узел добавляется справа от последнего вставленного. Это приводит к одному длинному списку. Обратите внимание: чем более "случайны" поступающие данные, тем более сбалансированным получается дерево.

Удаления производятся примерно так же - необходимо только позаботиться о сохранении структуры дерева. Например, если из дерева на рис. 3.4 удаляется узел 20, его сначала нужно заменить на узел 37. Это даст дерево, изображенное на рис. 3.5. Рассуждения здесь примерно следующие. Нам нужно найти потомка узла 20, справа от которого расположены узлы с большими значениями. Таким образом, нам нужно выбрать узел с наименьшим значением, расположенный справа от узла 20. Чтобы найти его, нам и нужно сначала спуститься на шаг вправо (попадаем в узел 38), а затем на шаг влево (узел 37); эти двухшаговые спуски продолжаются, пока мы не придем в концевой узел, лист дерева.

Рис. 3.4. Бинарное дерево после добавления узла 18

Рис. 3.5. Бинарное дерево после удаления узла 20

Реализация

В реализации алгоритма на Си операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в дереве. Каждый узел Node содержит указатели left, right на левого и правого потомков, а также указатель parent на предка. Собственно данные хранятся в поле data. Адрес узла, являющегося корнем дерева хранится в указателе root, значение которого в самом начале, естественно, NULL. Функция insertNode запрашивает память под новый узел и вставляет узел в дерево, т.е. устанавливает нужные значения нужных указателей. Функция deleteNode, напротив, удаляет узел из дерева (т.е. устанавливает нужные значения нужных указателей), а затем освобождает память, которую занимал узел. Функция findNode ищет в дереве узел, содержащий заданное значение.

// Коды для бинарных деревьев

typedef int T; /* type of item to be sorted */

#define compLT(a,b) (a < b)

#define compEQ(a,b) (a == b)

typedef struct Node_ {

struct Node_ *left; /* left child */

struct Node_ *right; /* right child */

struct Node_ *parent; /* parent */

T data; /* data stored in node */

} Node;

Node *root = NULL; /* root of binary tree */

Node *insertNode(T data) {

Node *x, *current, *parent;

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

* allocate node for data and insert in tree *

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

/* find x's parent */

current = root;

parent = 0;

while (current) {

if (compEQ(data, current->data)) return (current);

parent = current;

current = compLT(data, current->data) ?

current->left : current->right;

}

/* setup new node */

if ((x = malloc (sizeof(*x))) == 0) {

fprintf (stderr, "insufficient memory (insertNode)\n");

exit(1);

}

x->data = data;

x->parent = parent;

x->left = NULL;

x->right = NULL;

/* insert x in tree */

if(parent)

if(compLT(x->data, parent->data))

parent->left = x;

else

parent->right = x;

else

root = x;

return(x);

}

void deleteNode(Node *z) {

Node *x, *y;

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

* delete node z from tree *

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

/* y will be removed from the parent chain */

if (!z || z == NULL) return;

/* find tree successor */

if (z->left == NULL || z->right == NULL)

y = z;

else {

y = z->right;

while (y->left != NULL) y = y->left;

}

/* x is y's only child */

if (y->left != NULL)

x = y->left;

else

x = y->right;

/* remove y from the parent chain */

if (x) x->parent = y->parent;

if (y->parent)

if (y == y->parent->left)

y->parent->left = x;

else

y->parent->right = x;

else

root = x;

/* y is the node we're removing */

/* z is the data we're removing */

/* if z and y are not the same, replace z with y. */

if (y != z) {

y->left = z->left;

if (y->left) y->left->parent = y;

y->right = z->right;

if (y->right) y->right->parent = y;

y->parent = z->parent;

if (z->parent)

if (z == z->parent->left)

z->parent->left = y;

else

z->parent->right = y;

else

root = y;

free (z);

} else {

free (y);

}

}

Node *findNode(T data) {

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

* find node containing data *

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

Node *current = root;

while(current != NULL)

if(compEQ(data, current->data))

return (current);

else

current = compLT(data, current->data) ?

current->left : current->right;

return(0);

}

<DIV ALIGN=right></DIV>

Красно-черные деревья

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