О сортировке
Alone Coder
Пусть элементы массива a нумеруются от
0 до num-1 и нам надо отсортировать их по
возрастанию (сначала самые маленькие по
значению, потом всё больше и больше - и
так до максимального).
0
Вот тупая сортировка "каждый с каждым",
которая почему-то иногда удостаивается ме─
ста в литературе:
for (i = 0; i < num; i++) {
for (j = 0; j < num; j++) {
if (a[i] > a[j])
swap(a[i], a[j])
}
}
Здесь n*n проходов внутреннего цикла.
Вообще странно, кому пришло в голову срав─
нивать каждую пару элементов два раза.
Здесь результативны проходы только для
i>j, а их более ранние двойники бесполезны
- они сортируют в обратную сторону. Но ес─
ли мы уберём эти проходы-двойники, то по─
лучим ускорение всего в два раза, а дальше
никак. Это тупик.
1
Меняем алгоритм так, чтобы он обменивал
только соседние элементы массива. При этом
ускоряем его в те же 2 раза (будет (n-1)*
*(n-1)/2 проходов),используя факт,что мак─
симальный элемент окажется в конце массива
после первого же перебора ("всплывает").
Получается так называемая "пузырьковая со─
ртировка" - bubble sort.
for (i = num; i > 0; i--) {
for (j = 0; j < i; j++) {
if (a[j] > a[j+1])
swap(a[j], a[j+1])
}
}
Число обменов равно числу перемещений
элементов, делённому на 2. Число перемеще─
ний чисел равно количеству элементов, ум─
ноженному на среднее число перемещений для
элемента.
Число перемещений элемента равно: число
перемещений влево плюс число перемещений
вправо. (Да-да! Элемент, прежде чем найдёт
своё место в массиве, может двигаться как
пьяный матрос! Пример - элемент 2 в масси─
ве 4 2 1 3.)
Элемент [i] перемещается влево столько
раз, сколько бОльших его элементов было
слева в первоначальном массиве a[i]. В
среднем это будет i/2.
Элемент [i] перемещается вправо сто─
лько раз, сколько меньших его элементов
было справа в первоначальном массиве a[i].
В среднем это будет (num-i-1)/2.
Итого среднее число перемещений элемен─
та: (num-1)/2. Отсюда среднее число пе─
ремещений элементов: n*(num-1)/2. Отсюда
среднее число обменов: n*(num-1)/4, т.е.
примерно вдвое меньше, чем число проходов
внутреннего цикла.
Вот как выполняет наш алгоритм типичный
процессор (reg - это регистры):
for (reg_i = num; reg_i > 0; reg_i--) {
for (reg_j = 0; reg_j < reg_i; reg_j++) {
reg_aj=a[reg_j];
reg_aj1=a[reg_j+1];
if (reg_aj > reg_aj1) {
reg_temp=a[reg_j];
a[reg_j]=a[reg_j+1];
a[reg_j+1]=reg_temp
}
}
}
В среднем 2+(4/2)=4 обращения к массиву
за шаг! НАМ СТОЛЬКО НЕ НУЖНО!!!
2
Убираем 2 из 4 обращений к массиву вну─
три обмена.
for (reg_i = num; reg_i > 0; reg_i--) {
for (reg_j = 0; reg_j < reg_i; reg_j++) {
reg_aj=a[reg_j];
reg_aj1=a[reg_j+1];
if (reg_aj > reg_aj1) {
a[reg_j]=reg_aj1;
a[reg_j+1]=reg_aj
}
}
}
3
Убираем одно из 2 обращений к памяти
вне обмена.
for (reg_i = num; reg_i > 0; reg_i--) {
reg_aj=a[0];
for (reg_j1=1; reg_j1<=reg_i; reg_j1++) {
reg_aj1=a[reg_j1]; //!!!
if (reg_aj > reg_aj1) {
a[reg_j1]=reg_aj1;
a[reg_j1-1]=reg_aj;
};
else reg_aj=reg_aj1;
}
}
Теперь на каждом шаге мы обращается к
массиву в среднем 2 раза. Всего-навсего.
Всего-навсего? Подумайте хорошенько!!!
ПОЧЕМУ НЕ 1 РАЗ?! Зачем нужна эта чехарда
обменов,если нам надо всего лишь протащить
максимальные значения в конец массива???
Достаточно обменивать максимальное значе─
ние с последней ячейкой - и мы добьёмся
того же самого!
4
Убираем обмен, чтобы обращаться к мас─
сиву только 1 раз на каждом шаге. Заодно
исчезает декремент. Получаем сортировку
прямым поиском.
for (reg_i = num; reg_i > 0; reg_i--) {
reg_j=0; //current max index
reg_aj=a[0]; //current max number
for (reg_j1=1; reg_j1<=reg_i; reg_j1++) {
reg_aj1=a[reg_j1];
if (reg_aj > reg_aj1) {
reg_j=reg_j1; //current max index
reg_aj=reg_aj1; //current max number
};
};
a[reg_j]=a[reg_i];
a[reg_i]=reg_aj; //current max number
}
Итого мы получили по сравнению с перво─
начальным методом ускорение в 8 (восемь)
раз по числу обращений к массиву ((num-1)*
*(num-1)/2) и в 2 (два) раза по числу сра─
внений (тоже (num-1)*(num-1)/2).
Правда, мы не учли, что в каждом элеме─
нте массива может быть (и обычно есть) ещё
какая-либо информация, кроме значения
(value), по которому мы сортируем. Напри─
мер, для построения дерева Хаффмана элеме─
нты должны содержать частоту (это и будет
value) и - в качестве довеска - код симво─
ла. Для Z-сортировки полигонов value - это
Z-координата, а остальные координаты - до─
весок. Везде,где встречается "перемещение"
или "обмен" элементов,имеется в виду пере─
мещение ВСЕЙ информации, содержащейся в
элементах. Вышеприведённые программы будут
работать только если операция сравнения
сравнивает values элементов, а операция
присваивания копирует элемент целиком. Но
тогда reg-переменные скомпилируются уже не
как регистры, а как переменные в памяти -
это медленно!
5
Ускоряем:
for (reg_i = num; reg_i > 0; reg_i--) {
reg_j=0; //current max index
reg_aj=a[0].value; //current max number
for (reg_j1=1; reg_j1<=reg_i; reg_j1++) {
reg_aj1=a[reg_j1].value;
if (reg_aj > reg_aj1) {
reg_j=reg_j1; //current max index
reg_aj=reg_aj1; //current max number
};
};
swap(a[reg_j], a[reg_i])
}
При реализации этого алгоритма на ассе─
мблере, в случае частой сортировки малень─
ких массивов, можно учесть, что на момент
команды swap у нас уже есть в регистрах
value элемента a[reg_j].
6
Если мы уверены, что num достаточно ве─
лик,то мы можем использовать более сложные
алгоритмы.
Например, в алгоритме heap sort (если
это не лучший из алгоритмов внутренней со─
ртировки, то, во всяком случае, он проще и
быстрее,чем знаменитый quick sort) имеется
два этапа:
1) Превращаем массив в почти полное би─
нарное дерево,где каждый родитель не мень─
ше потомка. Требует до (num/2)*log2(num/2)
проходов, каждый из которых имеет 2.5 сра─
внений, 2 обращения к массиву, 2 инкремен─
та и одно умножение на 2.
2) Для j=num-1 до 1 повторяем следующую
операцию: обмен первого элемента массива с
j-м (исключается из дерева), потом исправ─
ление получившегося дерева. Каждое исправ─
ление требует до log2((j-1)/2) проходов
того же вида, что и в первом этапе.
Итого требуется где-то до
num*(log2(num)-1)
проходов указанного вида.
Пусть num=32. Тогда для heap sort тре─
буется до 256 обращений к массиву, до 320
сравнений,до 256+ инкрементов и до 128 ум─
ножений на 2. А для старого алгоритма (см.
параграф 5) - 496 обращений к массиву, 496
сравнений и 496+ инкрементов.
Вот статья про heap sort из журнала
Pixelate #5 (перевожу с английского, воль─
но исправляя и дополняя). Автор - Robert J
Ohannessian.
──────────────────────────────────────────
Heap, используемый в heap sort, - раз─
новидность бинарного дерева, являющегося
left-complete (т.е. заполняемого слева на─
право,причём переход на новый ярус не про─
исходит,пока не заполнен предыдущий). Каж─
дый узел heap'а должен содержать значение
(value) не меньшее, чем у каждого из 2 его
потомков (если они есть).
Пример:
76
/
45 34
/ /
6 12 8
Как видим, здесь каждый родитель не ме─
ньше потомка. Также видно,что дерево left-
complete, поскольку последний ярус запол─
няется слева направо,и все предыдущие пол─
ностью заполнены.Так что перед нами типич─
ный heap.
Чтобы сгенерировать этот начальный
heap, мы должны несколько раз использовать
алгоритм под названием 'reheapification'
(см. ниже). Предположим,что наш массив уже
переведён в heap.
Как разместить heap в памяти, не испо─
льзуя указателей и прочей мути? А вот как.
Просто-напросто в массив, ярус за ярусом:
Array: 76 45 34 6 12 8
Position: 0 1 2 3 4 5
Обратите внимание, что при добавлении в
массив новых элементов наш heap остаётся
left-complete - последний ярус заполняется
слева направо. Ещё обратите внимание, что
дочерние узлы узла номер i находятся в
ячейках i*2+1 и i*2+2. Однако встаёт воп─
рос: как мы можем гарантировать, что value
родителя не меньше, чем у его потомков?
Возьмём тот же пример. Предположим, что мы
добавили 102 в конец heap'а, то есть в ко─
нец массива:
76 45 34 6 12 8 102
что соответствует следующему дереву:
76
/
45 34
/ /
6 12 8 102
Это не heap. Чтобы сделать его heap'ом,
попытаемся обменять 102 с его родителем
(34). Получаем следующее дерево:
76
/
45 102
/ /
6 12 8 34
Уже ближе, но всё равно не heap. Повто─
ряем ту же операцию и получаем:
102
/
45 76
/ /
6 12 8 34
Теперь это heap.
Если вам интересно, то программа,реали─
зующая вышеописанное, такова:
/* Добавляет элемент 'value' в heap,
лежащий в массиве 'array'.Надо следить,
чтобы 'array' не переполнился */
void add_to_heap(int *array,
int *size,
int value) {
int i = *size;
/* Пишем value в конец массива, т.е. в
первую пустую ячейку heap'а */
array[*size] = value;
(*size)++;
/* Пока массив не heap, двигаем value
вверх */
while (i>0 && array[(i-1)/2]<array[i]) {
int temp = array[i];
array[i] = array[(i-1) / 2];
array[(i-1) / 2] = temp;
i = (i-1) / 2;
}
return;
}
Как вы видели, добавление 102 требует
лишь 2 итерации алгоритма. В худшем случае
требуется log2(n) итераций, где n - число
элементов дерева. То есть вставка одного
числа в heap имеет сложность O(ln(n)) [эта
запись означает, что с ростом n число опе─
раций асимптотически приближается к лога─
рифму n, умноженному на какой-то постоян─
ный коэффициент]. Таким образом,добавление
n чисел имеет сложность O(n*ln(n)). И это
для худшего случая!
Вы,конечно,спросите: "Ну и как эта каб─
балистика поможет отсортировать массив?"
Объясню.
Пусть мы имеем heap, который мы постро─
или в предыдущем примере. Он представлен
вот таким массивом:
102 45 76 6 12 8 34
Если мы возьмём первый элемент этого
массива и обменяем его с последним, то по─
лучим:
34 45 76 6 12 8 102
Понятно, что это уже не heap! Но подож─
дите. Мы будем теперь считать, что массив
стал на 1 элемент короче (n-1 элементов
вместо n). Точнее, разобьём массив на две
части. Первая будет деревом,а вторая - от─
сортированным массивом.(Будем шаг за шагом
уменьшать первую и увеличивать вторую.)
Итак, мы имеем:
34 45 76 6 12 8 - 102
( '-' будет разделять две эти части на на─
ших диаграммах,но на самом деле здесь один
массив.)
Поскольку мы пока не имеем heap, нам
следует провести 'reheapification'.Это тот
самый алгоритм, с помощью которого мы дол─
жны были построить heap на первом этапе
(если не помните,отмотайте текст назад:-).
Алгоритм reheapification очень простой.
Для конкретного родителя проверяем, нет ли
у него детей, больших его. Если таковые
найдутся,обмениваем родителя с самым боль─
шим из них и смотрим, нет ли теперь у него
детей, больших его... и т.д. Похоже на то,
что мы делали,добавляя 102, но теперь све─
рху вниз,а не снизу вверх. Сложность такая
же - O(ln(n)). Подпрограмма, которая про─
цитирована выше,нам не понадобится. Мы бу─
дем reheapifi'цировать только сверху вниз.
Например, пусть нам надо выполнить
reheapification, начиная с корня (в данном
случае 34).
34
/
45 76
/ /
6 12 8
Сравним его с детьми: 45 и 76. Большее
дитя - 76, и оно больше родителя (34), по─
этому мы переставляем его с родителем. Те─
перь 76 - родитель, а 45 и 34 - дети.
76
/
45 34
/ /
6 12 8
Далее надо таким же образом проверить,
что новоусыновлённый 34 не меньше его де─
тей - в данном случае одного ребёнка: 8.
Если всё в порядке,то конец алгоритма,ина─
че опять меняем местами и т.д. В данном
случае всё в порядке, поэтому конец.
Начальный heap мы строим, много раз по─
вторяя reheapification: начинаем с предпо─
следнего яруса (т.к. последний не имеет
детей) и кончаем первым (корнем). То есть
сначала вызываем reheapification для узла
номер (int)(n/2),потом для (int)(n/2)-1, и
т.д. до 0. В конце концов наверху будет
максимальное число, а все узлы,которые ле─
жат ниже, будут не меньше своих потомков
(ведь мы каждый из них reheapifi'цирова─
ли). Мы получили heap!
Но мы отвлеклись, так и не отсортировав
наш массив.Мы попытались разбить массив на
отсортированую и неотсортированную части,
потом сделали heap из неотсортированной
части. Если мы опять повторим ту операцию,
то есть вынем корневой элемент и поместим
его в отсортированную часть массива, то
получим:
8 45 34 6 12 - 76 102
Теперь у нас два отсортированных числа
- 76 и 102. Нанести, смыть, повторить, и в
конце концов получаем:
- 6 8 12 34 45 76 102
Массив отсортирован!
Посмотрим, как и почему это работает.
Имея heap,мы знаем,что корень heap'а (пер─
вый, точнее 0-й, узел) носит максимальное
значение. По определению. Значит, мы можем
переместить его в отсортированную часть
массива. Если мы после этого изъятия пере─
строим heap,то в новом heap'е корень будет
иметь новое максимальное значение. Другими
словами, второе по величине значение мас─
сива будет в новом корне. Мы опять имеем
право перетащить 0-й элемент массива в от─
сортированную часть. Повторив это для всех
элементов неотсортированной части,мы полу─
чим полностью отсортированный массив!
И насколько же хорош этот алгоритм сор─
тировки? Надо провести некоторый расчёт.
Первый этап нашего алгоритма - превращение
массива в heap. Для этого мы перебираем
каждый узел,имеющий детей (таких узлов по─
рядка n/2), и проводим для него reheapifi─
cation. Поскольку в reheapification требу─
ется не больше ходов,чем есть ярусов в де─
реве (а их порядка log2(n) ), то всё прев─
ращение в heap имеет сложность порядка
O((n/2)*log2(n))=O(n*log2(n)) =O(n*ln(n)).
Далее, вторым этапом - переброска корней в
отсортированную часть. Перестройка heap'а
после изъятия корня требует в худшем слу─
чае log2(n) ходов, а нам нужно делать эту
перестройку n-1 раз, итого выходит порядка
O(n*ln(n)) ходов.Поскольку первый этап то─
же имел сложность O(n*ln(n)), то весь ал─
горитм имеет сложность O(n*ln(n)). А у со─
ртировки методом перебора-пузырька-поиска,
как мы её ни оптимизировали,была сложность
O(n*n), в ней число ходов с ростом n росло
куда быстрее!
Я догадываюсь, что вам не терпится пос─
мотреть исходник. Вот он в том виде, как
использовался в игре Set Up Us The Bomb!!!
с небольшим изменением для сортировки по
возрастанию:
/* Macro to swap two numbers */
/* через XOR - для понта... */
#define SWAP(a, b) {
(a) ^= (b);
(b) ^= (a);
(a) ^= (b);
}
/* Macro for reheapification */
#define SORT_DOWN(pos,len) for (k=pos;;){
int right, left, max;
left = 2 * k + 1;
right = left + 1;
if (left >= len)
break;
else if ((right >= len)
|| (array[left] > array[right]))
max = left;
else
max = right;
if (array[k] > array[max])
break;
SWAP(array[k], array[max]);
k = max;
}
/* Sorts a list of ints using Heap Sort */
void sort_ints(int *array, int length) {
int i, k;
/* Строить heap из массива */
for (i = length / 2; i >= 0; i--)
SORT_DOWN(i, length);
for (i = length - 1; i > 0; i--) {
/*Перенести корень в сортированную часть*/
SWAP(array[i], array[0]);
/*Исправить heap в несортированной части*/
SORT_DOWN(0, i);
}
return;
}
──────────────────────────────────────────
В книге "Структуры данных для персона─
льных ЭВМ" (Й.Лэнгсам, М.Огенстайн, А.Те─
ненбаум. - М.: "Мир", 1989) этот алгоритм
называется "пирамидальной сортировкой".
Авторы предлагают исходник на Бейсике. Об─
ратите внимание на отличия от вышеприве─
дённого сишного исходника:
1. Начальное дерево строится не снизу
вверх, а сверху вниз (используя вышеизло─
женный алгоритм add_to_heap, который в Си-
версии не пригодился). Это требует вдвое
больше проходов,и хотя сами проходы короче
(их длины возрастают по мере заполнения
heap'а), в среднем получается проигрыш.
2. В reheapification вместо цепочки
swap'ов (4 обращения к массиву на каждом
шаге) использована цепочка простых присва─
иваний (2 обращения к массиву на каждом
шаге), родительский узел предварительно
запоминается и кладётся в массив в послед─
нюю очередь. Это хороший выигрыш.
3. Имеется ряд лишних инкрементов, кото─
рые можно оптимизировать.
4. Строки 5210-5250 по сути повторяют
строки 5290-5320, только с меньшим числом
вычислений - специально для корня.
5050 for k=2 to n 'у нас массив x(1..n)
5060 'вставить x(k) в существующую
'пирамиду размером k-1
5070 i=k
5080 y=x(k)
5090 j=int(i/2) 'j является отцом i
5100 if j<=0 then goto 5160
5110 if y<=x(j) then goto 5160
5120 x(i)=x(j)
5130 i=j
5140 j=int(i/2)
5150 goto 5100
5160 x(i)=y
5170 next k
5180 'мы удаляем x(1) и помещаем его в
'массиве в позицию, соответствующую
'его значению; затем перестраиваем
'пирамиду
5190 for k=n to 2 step -1
5200 y=x(k)
5210 x(k)=x(1)
5220 'переупорядочивание пирамиды
'порядка k-1; перемещение y в низ
'пирамиды на место, соответствующее
'его значению
5230 i=1
5240 j=2
5250 if (k-1>=3)and(x(3)>x(2)) then j=3
5260 'j является бОльшим сыном i в
'пирамиде размером k-1
5270 if j>k-1 then goto 5340
5280 if x(j)<=y then goto 5340
5290 x(i)=x(j)
5300 i=j
5310 j=2*j
5320 if j+1<=k-1
then if x(j+1)>x(j) then j=j+1
5330 goto 5260
5340 x(i)=y
5350 next k
В следующий раз я, возможно, напишу о
сортировке слиянием, которая,по моему мне─
нию, наиболее удобна для сортировки имён
файлов.
