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

    Один из самых необычных алгоритмов сортировки массива  - это HeapSort, в основе которого лежит алгоритм сортировки выбором, используется структура данных «куча» для быстрого нахождения максимального элемента, а также способ хранения двоичного дерева в линейном массиве. Разберёмся со всем по порядку.

    Сортировка выбором

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

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

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

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

    (2*N  + 1) + (2*(N - 1) + 1) + …
    + (2*K + 1) + … + 2*1 + 1 =
    = 2(N*N - N)/2 + N = N*N

    То есть, сложность алгоритма сортировки выбором - O(N2).

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

    Попробуем ускорить время работы алгоритмы сортировки.

    Больше всего времени уходит на поиск максимального элемента в неотсортированной части. Можно ли как-нибудь ускорить этот процесс? Да, можно, если использовать структуру данных «куча» или «пирамида». Это древовидная структура данных, в которой каждый дочерний элемент меньше родительского. На вершине кучи всегда находится максимальный элемент, поэтому его можно выбрать максимально быстро - всего за 1 операцию.

    Идея замечательная, но для её воплощения нужно решить ряд технических вопросов:

    1. создать древовидную структуру

    2. сформировать кучу из неотсортированных элементов

    3. уменьшить размер кучи после переноса максимума в отсортированную часть

    Создание древовидной структуры для кучи

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

    P = (x - 1) / 2
    L = 2x + 1
    R = 2x + 2

    Формирование кучи из неотсортированных элементов

    Единственное правило кучи: дочерние элементы меньше родительских. 

    Давайте опишем рекурсивный алгоритм 

    void heapify(int root, int size) 

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

    Откуда начать формирование кучи?

    У листьев дерева нет дочерних элементов, поэтому, они сразу удовлетворяют правилам и являются маленькими «кучками» из одного элемента. Поэтому мы можем пропустить все листовые элементы и начать формирование кучи с первого внутреннего узла -- им является родитель последнего листа.

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

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

    Будем продолжать вызывать функцию heapify() для всех элементов вплоть до корневого. Таким образом мы итеративно превратим неотсортированную часть массива в правильную кучу. 

    Сколько операций необходимо на этот процесс? Давайте рассмотрим на конкретном примере. Допустим, у нас 31 элемент в массиве. В нижней строчке 16 листов и мы их все пропускаем, получается 0*16 операций. Во второй строчке снизу у нас 8 элементов, и в каждом нужно будет выполнить одно действие, получается 1*8 операций. На третей строчке снизу - 4 элемента, в каждой строчке будет не более 2 действий, так как глубина везде 2, получается 2*4 операций. На следующей строке - 3*2, на верхней - 4*1. Сложим всё вместе:

    0*16 + 1*8 + 2*4 + 3*2 + 4*1 = 34 операций.

    В самом деле, на каждом новом уровне в два раза меньше элементов, а максимальная глубина увеличивается только на 1, то есть амортизированная сложность формирования кучи - O(N).

    Класс HeapSort с алгоритмом сортировки

    Перенос максимума в отсортированную часть и уменьшение кучи

    Самое простое и быстрое действие. Максимальный элемент всегда находится на вершине кучи. Его нужно обменять с последним листом кучи, который сразу переходит в отсортированную часть массива. Размер кучи после этого уменьшится на 1, а на вершине кучи окажется один из самых меньших значений массива, поскольку там оказался листовой элемент.

    Теперь нам нужно «перепирамидить» кучу -- вызвать алгоритм проверки для вершины, в процессе которого будут выполняться рекурсивные вызовы проверки для дочерних элементов, пока это будет необходимо. В худшем случае на это потребуется log 2 K операций, где K - текущий размер пирамиды.

    После N итераций пирамида исчезнет, все элементы окажутся в отсортированной части, сортировка завершена!

    Сложность сортировки не превышает O(N log 2 N).

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

    Статья была подготовлена в рамках набора на курс "Алгоритмы и структуры данных". 20 апреля я проведу бесплатный демо-урок на котором мы сначала реализуем алгоритм сортировки выбором, а потом превратим массив в пирамиду (кучу) и ускорим время поиска максимального элемента в неотсортированной части массива с линейного до логарифмического. В итоге у нас получится алгоритм Пирамидальной сортировки. Мы наглядно продемонстрируем работу алгоритма на визуальных примерах с конкретными числами. Участие в демо-уроке абсолютно бесплатное.

    Регистрация доступна по ссылке.

    OTUS
    Цифровые навыки от ведущих экспертов

    Комментарии 4

      0
      Для более простого объяснения алгоритм достаточно назвать «царь горы». Это более наглядное название происходящего.
        0

        В C# этот алгоритм может использоваться наравне с QuickSort при сортировке массива.

          +1

          Построение пирамиды — O(N) по времени. Почему так? На самом деле формирование кучи можно описать по другому. Мы идем с середины массива, и делаем просеивания для элементов на уровнях, без рекурсивного вызова. Допустим для упрощения, длина массива N = 2^n — 1, пирамида ровненькая. Просеивания для нижнего уровня нелистовых элементов — высотой 1, таких элементов N/4. Для уровня выше высота будет 2, там N/8 элементов, потом 3 и N/16 элементов, и т.д. Если это дело просуммировать, то получаем O(N)

            0
            Вы абсолютно правы!
            Я опишу этот вариант в статье.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое