Алгоритмы сортировки.

Пирамидальная сортировка.

Назовем пирамидой последовательность элементов

h_l , h_l+1 , ... , h_r

такую, что

h_i <= h_2i

h_i <= h_2i+1

для всякого i = l , ... , r/2

Геометрическая интерпретация пиромиды:

                 h₁
                /  \
               /    \
              /      \
             /        \
            /          \
          h₂            h₃
         / \            / \
        /   \          /   \
      h₄    h₅       h₆     h₇
     /	\  /  \     / \   /  \
    h₈  h₉ h₁₀ h₁₁  h₁₂ h₁₃ h₁₄ h₁₅

 Для последовательности 06 42 12 55 94 18 44

                 06
                /  \
               /    \
              /      \
             /        \
            /          \
          42            12
         / \            / \
        /   \          /   \
      55    94        18   44

Добавление элемента в готовую пирамиду.

     1. Новый элемент Х помещаем в вершину дерева.

     2. Смотрим на элемент слева и элемент справа - выбираем наименьший.

     3. Если этот элемент меньше Х - меняем их местами и идем у шагу 2. Иначе конец процедуры.

Фаза 1: построение пирамиды.

Пусть дан массив h₁ ... h_n . Ясно, что элементы h_{n/2 + 1} ... h_n уже образуют 'нижний ряд' пирамиды, так как не существует индексов i , j : j = 2*i ( или j = 2*i + 1 ). То есть тут упорядочивания не требуется.

На каждом шаге добавляется новый элемент слева и 'просеивается' на место. Вот иллюстрация процесса для пирамиды из 8-и элементов:

44  55  12  42  //  94  18  06  67
44  55  12  //  42  94  18  06  67
44  55  //  06  42  94  18  12  67
44  //  42  06  55  94  18  12  67
//  06  42  12  55  94  18  44  67

Фаза 2: сортировка.

Для того, чтобы рассортировать элементы, необходимо выполнить n шагов просеивания: после каждого шага очередной элемент берется с вершины пирамиды. На каждом шаге берем последний элемент Х, верхний элемент пирамиды помещается на его место, а Х просеивается на свое 'законное'. В этом случае необходимо совершить n - 1 шагов. Пример:

 06  42  12  55  94  18  44  67  //
 12  42  18  55  94  67  44  //  06
 18  42  44  55  94  67  //  12  06
 42  55  44  67  94  //  18  12  06
 44  55  94  67  //  42  18  12  06
 55  67  94  //  44  42  18  12  06
 67  94  //  55  44  42  18  12  06
 94  //  67  55  44  42  18  12  06

Ну вот мы м получили отсортированную последовательность, только в обратном порядке. Изменяя сравнения на противоположные, получаем функцию Heapsort на Паскале

Прекрасной характеристикой этого метода является то, что среднее число пересылок - (n*log n)/2 и отклонения от этого значения сравнительно малы.

Вверх по странице, к оглавлению и навигации.