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

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

Пирамидальная сортировка основана на использовании структуры данных пирамида (heap). Это структура данных представляет собой бинарное дерево. Каждый узел дерева соответствует элементу массива. Последний уровень заполняется слева направо.

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

Метод Parent(i) возвращает индекс родительского узла i:

private int parent(int i){
        return i/2;
}

Метод left(i) - получение индекса левого дочернего узла, где i - родительский узел:

private int left(int i){
        return 2*i;
}

Метод right(i) - получение индекса правого дочернего узла, где i - родительский узел:

private int right(int i){
        return 2*i + 1;
}

Замечание: Метод parent(i) возвращает наименьшее целое число, при передаче ему нечетного числа.

Невозрастающая пирамида

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

Неубывающая пирамида

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

Метод heapify(A,i) - поддерживает свойство невозрастающей пирамиды:

private void heapify(Integer i){
        int largest;
        int left = left(i);
        int right = right(i);

        if ((left < heapSize) && (arr[left] > arr[i])){
                largest = left;
        }
        else{
                largest = i;
        }

        if ((right < heapSize) && (arr[right] > arr[largest])){
                largest = right;
        }

        if (i != largest){
                int temp = arr[i];
                arr[i] = arr[largest];
                arr[largest] = temp;
                this.heapify(largest);
        }
}

В методе есть дополнительные проверки, типа (left < heapSize) и (right < heapSize). Методы left(i) и right(i) могут вернуть такой индекс, который не входит в пирамиду. Метод является рекурсивным, после обмена значениями дочерних узлов и родительского узла, повторно вызывается этот же метод, которому передается индекс узла с наибольшим значением.

Конструктор Heap(A) - создает невозрастающую пирамиду из элементов массива:

public Heap(Integer A[]){
        arr = A;
        heapSize = A.length;

        // создаем пирамиду
        for (int i = arr.length/2 - 1; i >= 0; i--){
                heapify(i);
        }
}

Функция heapSort(A) - пирамидальная сортировка.:

public void heapSort(){
        int arrLength = heapSize;

        for (int i = arrLength-1; i >= 1; i--){
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;

                --heapSize;
                heapify(0);
        }
}

В теле цикла значениями обмениваются корневой узел пирамиды arr[0] и последний элемент пирамиды (leaf node). После чего, размер пирамиды уменьшается, узел таким образом отсекается, и вызывается метод поддержания свойства невозрастания пирамиды heapify(0). Вызов метод нужен потому, что в корне пирамиды после обмена содержится наименьшее значение.

Анализ времени выполнения алгоритма¶

Метод left(i) выполняется очень быстро, путем битового сдвига числа i влево на одну позицию:

i = 3 = 11;
i = 2*3 = 110

i = 8 = 1000
i = 8*2 = 10000

Метод right(i) тоже выполняется очень быстро, путем битового сдвига числа i влево на одну позицию и установки младшего бита в единицу:

i = 3 = 11;
i = 2*3 + 1 = 111

i = 8 = 1000
i = 8*2 + 1 = 1001

Время работы метода heapify(i) в заданном узле i, вычисляется как время theta (1), необходимое для исправления отношений между элементами arr[i], arr[left(i)] или arr[right(i)], плюс время работы метода с поддеревом, корень которого находится в одном из дочерних узлов i. Время работы метода heapify(i) c узлом i, находящимся на высоте h, можно выразить как О(h) или O(lgn);

Высота узла определяется как количество его предков. Высоту дерева определяют по высоте его узлов листьев (leaf nodes).

Время работы метода heapsort() равно О(nlgn), поскольку вызов метода Heap() требует времени O(n), а каждый из n-1 вызовов метода heapify - времени O(lgn)

Сравнение со временем выполнения других алгоритмов сортировки¶