Файл: Углубленное изучение основных алгоритмов сортировки данных.pdf

Рис. 3: Первый проход быстрой сортировки

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

Наиболее часто используется середина области, т.е. элемент с индексом (l + r)/2. При таком подходе используются быстрые операции сложения и деления на два, и в целом он работает достаточно неплохо. Однако в некоторых задачах, где сутью является исключительно сортировка, хитрое жюри специально подбирает тесты так, чтобы «завалить» стандартную быструю сортировку с выбором опорного элемента из середины. Стоит заметить, что это очень редкая ситуация, но все же стоит знать, что можно выбирать произвольный элемент с индексом m так, чтобы выполнялось неравенство l ≤ m ≤ r. Чтобы это условие выполнялось, достаточно выбрать произвольные два числа x и y и выбирать m исходя из следующего соотношения: m = (x * l + y * r)/(x + y). В целом такой метод будет незначительно проигрывать выбору среднего элемента, т.к. требует двух дополнительных умножений.

Чтобы воспользоваться быстрой сортировкой, необходимо передать в функцию левую и правую границы сортируемого массива (т.е., например, вызов для массива a будет выглядеть как quick_sort(a, 0, n-1).

Алгоритм быстрой сортировки в среднем использует O(N log N) сравнений и O(N log N) присваиваний (на практике даже меньше) и использует O (log N) дополнительной памяти (стек для вызова рекурсивных функций). В худшем случае алгоритм имеет сложность O(N²) и использует O(N) дополнительной памяти, однако вероятность возникновения худшего случая крайне мала: на каждом шаге вероятность худшего случая равна 2/N, где N — текущее количество элементов.

Рассмотрим возможные оптимизации метода быстрой сортировки.

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

Во-вторых, как мы знаем, вызов функции — достаточно накладная операция, а для небольших массивов быстрая сортировка работает не очень хорошо. Поэтому, если при вызове функции сортировки в массиве находится меньше, чем K элементов, разумно использовать какой-либо нерекурсивный метод, например, сортировку вставками или выбором. Число K при этом выбирается в районе 20, конкретные значения подбираются опытным путем. Такая модификация может дать до 15% прироста производительности.

---

Быструю сортировку можно использовать и для двусвязных списков (т.к. в ней осуществляется только последовательный доступ с начала и с конца), но в этом случае возникают проблемы с выбором опорного элемента — его приходится брать первым или последним в сортируемой области. Эту проблема можно решить неким набором псевдослучайных перестановок элементов списка, тогда даже если данные были подобраны специально, эффект нейтрализуется.

Сортировка слияниями также основывается на идее, которая уже была нами затронута при рассмотрении алгоритма поиска двух максимальных элементов. В этом алгоритме мы сначала разобьем элементы на пары и упорядочим их внутри пары. Затем из двух пар создадим упорядоченные четверки и т.д.

Рис.4. Алгоритм сортировки слияниями

Интерес представляет сам процесс слияния: для каждой из половинок мы устанавливаем указатели на начало, смотрим, в какой из частей элемент по указателю меньше, записываем этот элемент в новый массив и перемещаем соответствующий указатель.

Опишем функцию слияния следующим образом:

void merge(int a[], int b[], int c, int d, int e) {

int p1=c, p2=d, pres=c; while (p1 < d && p2 < e) if (a[p1] < a[p2])

b[pres++] = a[p1++]; else

b[pres++] = a[p2++]; while (p1 < d)

b[pres++]=a[p1++]; while (p2 < e)

b[pres++]=a[p2++]; }

Здесь a — исходный массив, b — массив результата, end — указатели на начало первой и второй части соответственно, е — указатель на конец второй части.

Далее опишем довольно хитрую нерекурсивную функцию сортировки слиянием:

void merge_sort(int a[], int n) {

int *temp, *a2=a, *b=(int*)malloc(n*sizeof(int)), *b2;

int c, k = 1, d, e;

b2=b;

while (k <= 2*n) {

for (c=0; c<n; c+=k*2) { d=c+k<n?c+k:n; e=c+2*k<n?c+2*k:n; merge(a2, b, c, d, e); }

temp = a2; a2 = b; b = temp; k *= 2;

}

for (c=0; c<n; c++)

a[c] = a2[c]; free(b2); }

Рекурсивная реализация сортировки слияними несколько проще, но обладает меньшей эффективностью и требует O(logN) дополнительной памяти.

Алгоритм имеет сложность O(N logN) и требует O(N) дополнительной памяти.

В оригинале этот алгоритм был придуман для сортировки данных во внешней памяти (данные были расположены в файлах) и требует только последовательного доступа. Этот алгоритм применим для сортировки односвязных списков.

Сортировка подсчетом может использоваться только для дискретных данных. Допустим, у нас есть числа от 0 до 99, которые нам следует отсортировать. Заведем массив размером в 100 элементов, в котором будем запоминать, сколько раз встречалось каждое число (т.е. при появлении числа будем увеличивать элемент вспомогательного массива с индексом, равным этому числу, на 1). Затем просто пройдем по всем числам от 0 до 99 и выведем каждое столько раз, сколько оно встречалось. Сортировка реализуется следующим образом:

---

for (i=0; i<MAXV; i++)

c[i] = 0; for (i=0; i<n; i++)

c[a[i]]++; k=0; for (i=0; i<MAXV; i++)

for (j=0; j<c[i]; j++) a[k++]=i;

Здесь MAXV — максимальное значение, которое может встречаться (т.е. все числа массива должны лежать в пределах от 0 до MAXV — 1).

Алгоритм использует О (MAXV) дополнительной памяти и имеет сложность 0(N + MAXV). Его применение дает отличный результат, если MAXV намного меньше, чем количество элементов в массиве.

Алгоритм сортировки подсчетом чрезвычайно привлекателен своей высокой производительностью но она ухудшается при возрастании MAXV, также резко возрастают требования к дополнительной памяти. Фактически, невозможно осуществить сортировку подсчетом для переменных типа unsigned int (MAXV при этом равно 2³²).

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

Для примера приведем таблицу 1, в первом столбце которой расположены исходные данные, а в последующих — результат сортировки по разрядам.

Таблица 1

Пример для поразрядной сортировки

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

После этого будем проходить по всему исходному массиву, смотреть на текущее значение разряда (i), записывать текущее число во вспомогательный массив (b) на позицию с[i], а затем увеличивать с[i] (чтобы новое число с таким же значением текущего разряда не легло поверх уже записанного).

Пусть количество знаков в числе равно k, а количество возможных значений равно m (система счисления, использованная при записи числа). Тогда количество присваиваний, производимое алгоритмом, будет равно О(k*N + k*m), а количество дополнительной памяти — O(N + k*m).

Приведем эффективную реализацию поразрядной сортировки для беззнаковых 4-байтных чисел (unsigned int). Мы будем использовать 4 разряда, каждый из которых равен байту (система счисления с основанием 256). Эта реализация использует несколько хитростей, которые будут пояснены ниже.

---

void radix_sort(unsigned int a[], int n) {

unsigned int *t, *a2=a;

unsigned int *b=(unsigned int*) malloc(n*sizeof(int));

unsigned int *b2;

unsigned char *bp;

int i, j, npos, temp;

int c[256][4];

b2 = b;

memset(c, 0, sizeof(int)*256*4);

bp = (unsigned char*) a;

For(i,n)

For (j,4) { c[*bp][j]++; bp++; } For(j,4) { npos = 0; For(i,256) { temp = c[i][j];

c[i][j] = npos; npos += temp; } } For(j,4) {

bp = (unsigned char*) a2 + j; For(i,n) {

b[c[*bp][j]++] = a2[i]; bp += 4; }

t=a2;a2=b;b=t; }

free(b2); }

Функция memset используется для заполнения заданной области памяти нулями (обнуление массива), она находится в библиотеке string.h. Всю таблицу сдвигов (с) мы будем строить заранее для всех 4 разрядов. Для эффективно доступа к отдельным байтам мы будем использовать указатель bp типа unsigned char * (тип char как раз занимает 1 байт и может трактоваться как число). Затем мы формируем модифицированную таблицу и проводим собственно функцию расстановки чисел по всем 4 разрядам.

Внимательный читатель заметит в приведенной функции несколько мест, которые на первый взгляд кажутся ошибочными. Хотя в текстовом описании мы и говорили, что следует сортировать, начиная с последних разрядов, в реализации мы начинаем с первых байтов. Это объясняется тем, что в архитектуре x86 числа хранятся в «перевернутом» виде — это было сделано для совместимости с младшими моделями.

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

Вообще говоря, далеко не обязательно так сильно связывать поразрядную сортировку с аппаратными средствами. Более того, основное удобство поразрядной сортировки состоит в там, что с ее помощью можно сортировать сложные структуры, такие как даты, строки (массивы) и другие структуры со многими полями.

• 1. Быстродействующие методы сортировки

Древовидными называют методы сортировки, реализацию которых можно представить в виде дерева. Узлы дерева отображают части сортируемого массива. Методом мы называем множество алгоритмов, объединенных общей идеей, различия которых второстепенны. Пред­метом исследования являются метод QuickSort (идея метода — разделение массива и незави­симое упорядочение его частей), метод слияния (идея — поэтапное объединение упорядочен­ных частей массива) и метод пирамидальной сортировки (идея — упорядоченный выбор запи­сей с помощью пирамиды). Эти три метода обладают наилучшей асимптотической оценкой времени сортировки T = O(n log2n) в классе алгоритмов, использующих сравнения ключей; n — число записей в массиве.

---

Большими будем называть массивы, занимающие область памяти размером D десятки мегабайт и более. Через R обозначим размер сортируемых запи­сей. Классический алгоритм QuickSort обозначен именем A. Ближайшее к Х целое, не меньшее Х, обозначается как ^┌x^┐.

Наши исследования свидетельствуют о том, что пирамидальная сортировка [4] не конкурен­тоспособна в случаях, когда D в несколько раз больше кеша самого нижнего уровня, т.е. именно при сортировке больших массивов. Это вызвано худшей локальностью, чем в методе QuickSort и методе слияния, выражающейся в большей частоте перезагрузки кешей всех уровней, поэтому среднее время доступа к данным существенно больше, чем в методе QuickSort. Чтобы изучить этот эффект, улучшенную пирамидальную сортировку сравнивали по времени с улучшенной реализацией метода QuickSort, обозначаемой ниже как алгоритм C. В табл. 2 для R = 16 и разных значений n приведено полученное экспериментально среднее время сорти­ровки, Tc в миллисекундах.

Таблица 2

Экспериментальное среднее время сорти­ровки

Время Tc работы алгоритма C хорошо аппроксимируется выражением k_cn log₂n, где k_c — коэффициент, зависящий от типа компьютера. Обозначим через g отношение T_p/T_c, где Tp — время пирамидальной сортировки. Значение g возрастает приблизительно от 1,6 до 4,5 для n = 10⁸. Это свидетельствует о том, что время T_p растет быстрее, чем число операций, которое согласно теории определяется выражением k_pn log₂n, где k_p — коэффициент, т.е. сказывается увеличение удельного времени доступа к данным. Значение g и темп его изменения зависят от размера записи R и типа компьютера, точнее, от параметров иерархической структуры его памяти. В любом случае существует область больших значений n, где время T_p в несколько раз больше T_c. Это утверждение справедливо для всех разновидностей пирамидальной сортировки.

Чтобы сравнить метод слияния и метод QuickSort, рассмотрим последние результаты их оптимизации. Под оптимизацией сортировки [4] обычно понимается приближение среднего числа сравнений ключей к теоретико-информационному пределу log₂(n!). В [7] для сортировки был выведен нижний предел n + H_n – 2 среднего числа транспозиций записей — перемещений записей или обмена их местами (H_n — гармоническое число). Сокращение числа транспозиций также будем называть оптимизацией. Под всесторонней оптимизацией будем понимать умень­шение среднего числа как основных действий, так и массовых вспомогательных действий, для которых может быть известен теоретический минимум.

---