Info Guide #09 31 июля 2006

Программирование

For Coderz - О сортировке элементов массива.

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

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