Из журнала Info Guide #9, Рязань, 08.2006


        О сортировке
        
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

   В  следующий  раз я, возможно, напишу о
сортировке слиянием, которая,по моему мне-
нию, наиболее  удобна  для сортировки имён
файлов.