В разделе 04.03 (стр. 145-155) книги Скиена тема сортировки рассматривается как лаборатория для изучения принципов разработки алгоритмов. В следующих разделах будут представлены различные алгоритмы, порождённые алгоритмами сортировки.

Изучение алгоритмов сортировки начнётся с рассмотрения структур данных. Объясняется это тем, что одним из методов улучшения алгоритмов сортировки является использование подходящих под задачу структур данных.

В качестве первого примера приводится алгоритм сортировки методом выбора (в цикле извлекается наименьший оставшийся элемент из неотсортированной части входных данных). Алгоритм на языке C:

void selection_sort(item_type s[], int n) {
    int i, j; /* счетчики */
    int min;  /* индекс наименьшего элемента */

    for (i = 0; i < n; i++) {
        min = i;
        for (j = i + 1; j < n; j++) {
            if (s[j] < s[min]) {
                min = j;
            }
        }
        std::swap(s[i], s[min]);
    }

Массив делится на отсортированную и не отсортированную части. Далее среди неотсортированной части ищется наименьший элемент. Найденный элемент меняется местами с элементом i массива, после чего цикл повторяется. Итоговое время выполнения всего алгоритма O(n^2).

Алгоритм можно улучшить, если выбрать подходящую структуру данных. Предлагается заменить исходную структуру данных на структуру с реализацией очереди с приоритетами - пирамидальную или сбалансированное двоичное дерево. Использование такой реализации очереди с приоритетами позволяет ускорить сортировку методом выбора с O(n^2) до O(nlogn).

Подчёркивается, что пирамидальная сортировка - это не что иное, как реализация сортировки методом выбора с применением удачной структуры данных.

Пирамида - простая структура данных, реализующая очередь с приоритетами (поддерживает вставку и поиск наименьшего элемента). Принцип работы основан на поддержании порядка частичной отсортированности (массив отсортирован, но не до конца). Пирамида определяется как двоичное дереве, в котором значение ключа каждого узла доминирует над значениям ключа каждого из его потомков.

В качестве примера приводится неубывающая пирамида дат значимый событий в истории США (рис. 4.2., стр. 146):

Пирамиду можно реализовать как двоичное дерево с указателями, но также это можно сделать и без них. Данные будут сохранятся в виде массива ключей, а позиции ключей использоваться в роли неявных указателей:

typedef struct {
    item_type q[PQ_SIZE+1];  /* Тело очереди */
    int n;                   /* Количество элементов очереди */
} priority_queue;

Корневой узел сохраняется в первой ячейке массива, его потомки - во второй и третьей соответственно. Для узла в позиции k левый потом находится в позиции 2k, правый в 2k+1, а его родитель в позиции ⌊k/2⌋ (целочисленное деление). Таким образом мы можем перемещаться по дереву без указателей, а используя лишь простые арифметические операции.

int pq_parent(int n) {
    if (n == 1) {
        return(-1);
    }
    return((int) n/2); /* явно вычисляем floor(n/2) */
}

int pq_young_child(int n) {
    return(2 * n);
}

Главный недостаток такого представления: необходимость в том, чтобы дерево было заполненным слева направо (полным). Если же дерево высокое, но с малым количеством узлов (разрежённое), то выделение памяти под массив 2^(n-1) нерационально.

Однако в пирамиде всегда заполняются все уровни, кроме последнего. Он заполняется слева направо. Это гарантирует, что высота пирамиды из n элементов логарифмическая: h = ⌈log(n+1)⌉ (округление в большую сторону). Поэтому для хранения n ключей достаточно массива n элементов.

Такое неявное представление двоичных деревьев экономит память, но также делает структуру менее гибкой, чем представление с использованием указателей. К примеру: сохранение деревьев с произвольной топологией (не полных деревьев) влечёт за собой использование большого объёма памяти, а перемещение поддеревьев требует перемещения всех элементов, а не изменения одного указателя.

Такое отсутствие гибкости не позволяет использовать эту идею для представления двоичных деревьев поиска. Однако, для пирамид она подходит.

Пирамида создаётся пошагово, путём вставки нового элемента в самую левую ветку массива (в n+1 ячейку предыдущей пирамиды из n элементов). Это гарантирует сохранение сбалансированной формы дерева.

Однако, при такой вставке не гарантируется сохранения свойства доминирования. Эта проблема решается путём сравнения нового элемента со своим родителем. Если элемент меньше своего родителя (для неубывающей пирамиды), то они меняются местами. Процесс повторяется до тех пор, пока новый элемент не встанет на своё место или не достигнет корня.

Поскольку на каждом шаге корень поддерева заменяется элементом с большим уровнем доминирования, то порядок доминирования сохраняется во всех других частях пирамиды.

void pq_insert(priority_queue *q, item_type x) {
    if (q->n >= PQ_SIZE) {
        printf("Warning: priority queue overflow!\n");
    } else {
        q->n = (q->n) + 1;
        q->q[q->n] = x;
        bubble_up(q, q->n);
    }
}

void bubble_up(priority_queue *q, int p) {
    if (pq_parent(p) == -1) {
        return; /* Корень */
    }

    if (q->q[pq_parent(p)] > q->q[p]) {
        pq_swap(q, p, pq_parent(p));
        bubble_up(q, pq_parent(p));
    }
}

На каждом уровне обмен элементов местами занимается постоянное время O(1). А поскольку высота пирамиды из n элементов равна ⌊logn⌋ и в худшем случае новому элементу нужно подняться от самого низа до самого верха за время O(logn), то каждая вставка занимает самое большое время O(1) * O(logn) = O(logn).

Таким образом, пирамиду из n элементов можно создать посредством n таких вставок за время O(nlogn).

void pq_init(priority_queue *q) {
    q->n = 0;
}

void make_heap(priority_queue *q, item_type s[], int n) {
    int i; /* счетчик */

    pq_init(q);
    for (i = 0; i < n; i++) {
        pq_insert(q, s[i]);
    }
}

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

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

Проблемный элемент продвигается вниз пузырьковым методом до тех пор, пока он не начнёт доминировать над своими потомками или не станет листом. Данная операция называется восстановлением пирамиды (heapify), поскольку она сливает вместе две пирамиды (поддеревья под исходным корнем) с новым ключом.

item_type extract_min(priority_queue *q) {
    int min = -1; /* Минимальное значение (заглушка) */

    if (q->n <= 0) {
        printf("Warning: empty priority queue.\n");
    } else {
        min = q->q[1];

        q->q[1] = q->q[q->n];
        q->n = q->n - 1;
        bubble_down(q, 1);
    }
    return(min);
}

void bubble_down(priority_queue *q, int p) {
    int c;         /* Индекс потомка */
    int i;         /* Счетчик */
    int min_index; /* Индекс наименьшего потомка */

    c = pq_young_child(p);
    min_index = p;

    for (i = 0; i <= 1; i++) {
        if ((c + i) <= q->n) {
            if (q->q[min_index] > q->q[c + i]) {
                min_index = c + i;
            }
        }
    }

    if (min_index != p) {
        pq_swap(q, p, min_index);
        bubble_down(q, min_index);
    }
}

Для достижения позиции листа требуется ⌊log⁡n⌋ (высота дерева) исполнений процедуры bubble_down (Листинг 4.5), каждое из которых исполняется за линейное время O(1). Таким образом, удаления корня занимает время O(1) * O(logn) = O(logn).

Объединяя выше сказанное, можем сказать, что пирамидальная сортировка работает так:

• Из исходного массива n элементов строится пирамида.
• Из полученной пирамиды n раз извлекается наименьший элемент и записывается в итоговый массив.

Каждое извлечение занимает время O(logn). Процедура повторится n раз, значит итоговое время работы пирамидальной сортировки O(nlogn).

void heapsort(item_type s[], int n) {
    int i;                 /* Счетчик */
    priority_queue q;      /* Память для пирамидальной сортировки */

    make_heap(&q, s, n);

    for (i = 0; i < n; i++) {
        s[i] = extract_min(&q);
    }
}

Сортировка реализованная в приведённом коде не выполняется на месте (Сортировка на месте - сортировка внутри того же самого массива, который был дан на вход. Не создаётся второй массив для копирования отсортированных данных).

Исходный массив s не меняется, а отсортированные элементы записываются в него из временной очереди q. Реализации пирамидальной сортировки на месте существуют, но в представленном коде используется дополнительная память под очередь с приоритетами.

Существует способ создания пирамиды быстрее чем за время O(nlogn) с применением той же процедуры bubble_down (Листинг 4.5). Мы можем применять её не сверху вниз, а снизу вверх.

Скопируем все n элементов в массив очереди в произвольном порядке. Форма дерева будет правильная, но свойство доминирования в таком дереве не выполняется. Будем рассматривать массив с конца (от последнего элемента к первому). Элементы на позиция от n/2 до n будут являться листьями, они сами по себе являются правильными пирамидами состоящими из одного элемента. Мы начнём обрабатывать узлы на позициях от n/2 + 1 до 1, ведь у них есть потомки. Процедура bubble_down опускает узел i ∈ [1,n/2] вниз, объединяя две уже готовые пирамиды в одну. К моменту обработки узла i ∈ [1,n/2] его потомки гарантированно будут являться правильными пирамидами.

Таким образом, мы можем создать пирамиду выполнив n/2 вызовов bubble_down.

void make_heap_fast(priority_queue *q, item_type s[], int n) {
    int i; /* Счетчик */

    q->n = n;
    for (i = 0; i < n; i++) {
        q->q[i + 1] = s[i];
    }

    for (i = q->n / 2; i >= 1; i--) {
        bubble_down(q, i);
    }
}

Максимальное время выполнения процедуры bubble_down - O(logn), пусть количество вызовов будет n, значит общее время выполнения O(nlogn). Это время является верхним пределом, так как только последняя вставка требует ⌊lgn⌋ шагов. Время выполнения процедуры bubble_down пропорционально высоте пирамид, слияние которых она осуществляет. Узлов высотой h в пирамиде будет максимум ⌈n/2^(k+1)⌉. Итоговые затраты на создание пирамиды составляют:

$$\sum_{h=0}^{\lfloor \lg n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil h \le n \sum_{h=0}^{\lfloor \lg n \rfloor} \frac{h}{2^h} \le 2n.$$

Данная сумма сходится к линейной функции. В итоге, мы можем создать пирамиду за линейное время O(n).

Даже с учётом того, что время создания и ускорилось с O(nlogn) до O(n), сама сложность пирамидальной сортировки остаётся O(nlogn). Это происходит из-за того, что основное время тратится не на построение пирамиды, а на n операций извлечения минимума, каждая из которых занимает время O(logn).

Пусть перед нами стоит задача: для пирамиды из n элементов и числа x разработать эффективный метод, определяющий, является ли k-й элемент пирамиды больше или равенx. То есть, нам нужно узнать, наберется ли в пирамиде хотя бы k элементов, которые меньше x. В наихудшем случае время исполнения алгоритма должно быть равным O(k).

На ум сразу могут прийти два решения, но они будут не самыми эффективными:

1. k раз вызвать extract_min (Листинг 4.5) и сравнить с x. Это даст нам больше информации, чем требует задача, но для этого требуется время O(klogn).
2. Просмотреть элементы первых k уровней пирамиды ($2^k$ - 1 штук), ведь наименьший k-й элемент не может находится глубже, чем на k-м уровне пирамиды. Это займёт время O(min(n,2^k).

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

Начиная проверку с корня, сравниваем, если он меньше чем x, то увеличиваем счётчик найденных элементов и рекурсивно проверяем его левого и правого потомков. Если текущий узел оказывается больше или равен x, то прекращаем обход этой ветки. Рекурсия завершится, когда счётчик достигнет значения k, или обход не завершится полностью.

int heap_compare(priority_queue *q, int i, int count, int x) {
    if ((count <= 0) || (i > q->n)) {
        return(count);
    }

    if (q->q[i] < x) {
        count = heap_compare(q, pq_young_child(i), count - 1, x);
        count = heap_compare(q, pq_young_child(i) + 1, count, x);
    }

    return(count);
}

Мы проверяем только те узлы, чьи значения меньше x. Количество таких узлов не может первышать k (иначе мы бы уже нашли k таких элементов). Для каждого проверяемого узла мы делаем не более двух рекурсивных вызовов. В итоге, проверенно будет 2k + 1 узлов, что займет время O(k).

Раздел 04.03.154 Сортировка вставками реализован участником: Путинцев.А.А.

1. Стивен Скиена - "Алгоритмы. Руководство по раразобке" - 2022 (стр. 145-155)
2. Роджер Пенроуз - "Новый ум короля" - 2008