Файл: Алгоритмы сортировки данных.pdf

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

Сама сортировка будет состоять из создания кучи из массива и Nпереносов элементов с вершины кучи с последующим восстановлением свойства кучи:

Всего в процессе работы алгоритма будет выполнено 3 х N/2 — 2 вызова функции down_heap, каждый из которых занимает O(logN). Таким образом, мы и получаем искомую сложность в O(NlogN), не используя при этом дополнительной памяти. Количество присваиваний также составляет O(NlogN).

Пирамидальную сортировку следует осуществлять, если из условия задачи понятно, что единственной разрешенной операцией является «проталкивание» элемента по куче, либо в случае отсутствия дополнительной памяти.

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

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

Рис. 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(NlogN) и требует 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). Эта реализация использует несколько хитростей, которые будут пояснены ниже.

voidradix_sort(unsignedinta[], intn) {

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 числа хранятся в «перевернутом» виде — это было сделано для совместимости с младшими моделями.

---

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

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

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

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

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

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

---