ОСНОВНЫЕ ИДЕИ И ХАРАКТЕРИСТИКИ ПРИМЕНЯЕМЫХ, МЕТОД СОРТИРОВКИ - Структуры и алгоритмы обработки данных

МЕТОДОВ

МЕТОД СОРТИРОВКИ

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

Пирамидальная сортировка основана на алгоритме построения пирамиды. Последовательность aI, aI+1,...,aK называется (i, k)-пирамидой, если неравенство

AJ?min(a2j, а2j+1) (*)

Выполняется для каждого j, j=i,...,k для которого хотя бы один из элементов a2j, a2j+1 существует.

Например, массив А является пирамидой, а массив В не является.

А=(а2 , а3 , а4 , а5 , а6 А7 , а8 )=(3, 2, 6, 4, 5, 7)

В=(b1, b2, b3, b4, b5, b6, b7)=(3, 2, 6, 4, 5, 7)

Свойства пирамиды

    1. Если последовательность aI, aI+1,...,аK-1, aK является (I, k)-пирамидой, то последовательность aI+1,...,aK-1, полученная усечением элементов с обоих концов последовательности, является (I+1, k-1)пирамидой. 2. Если последовательность a1...aN - (1, n)-пирамида, то а1 - минимальный элемент последовательности. 3. Если a1, a2...,aN/2,aN/2+1,...aN-произвольная последовательность, то последовательность aN/2+1,...,aN является (N/2+1, n)-пирамидой.

Процесс построения пирамиды выглядит следующим образом. Дана последовательность aS+1,...,aK, которая является (S+1, k)-пирамидой. Добавим новый элемент х и поставим его на S-тую позицию в последовательности, т. е. пирамида всегда будет расширяться влево. Если выполняется (*), то полученная последовательность - (S, k)-пирамида. Иначе найдутся элементы a2s+1,a2s такие, что либо a2s < aS либо a2s+1 < aS.

Пусть имеет место первый случай, второй случай рассматривается аналогично. Поменяем местами элементы aS и a2s. В результате получим новую последовательность aS',aS+1,..., a2s',..., aK. Повторяем все действия для элемента a2s' и т. д. пока не получим (S, k)-пирамиду.

Пирамидальная сортировка производится в два этапа. Сначала строится пирамида из элементов массива. По свойству (3) правая часть массива является (N/2+1, n)-пирамидой. Будем добавлять по одному элементу слева, расширяя пирамиду, пока в нее не войдут все элементы массива. Тогда по свойству (2) первый элемент последовательности - минимальный.

Произведем двустороннее усечение: уберем элементы a1,aN. По свойству (1) оставшаяся последовательность является (2, n-1)-пирамидой. Элемент a1 поставим на последнее место, а элемент aN добавим к пирамиде a2,...,aN-1 слева. Получим новую (1, N-1)-пирамиду. В ней первый элемент является минимальным. Поставим первый элемент пирамиды на позицию N-1, а элемент aN-1 добавим к пирамиде a2,...,aN-1, и т. д. В результате получим обратно отсортированный массив.

Величины М и С в процессе построения (L, R)-пирамиды имеют следующие оценки MПир?log (R/L)+2, CПир?2 log (R/L)

Общее количество операций сравнений и пересылок для пирамидальной сортировки: C ? 2N log N+N+2, M ? N log N+6.5N-4. Таким образом, С=O(N log N), М=O(N log N) при N > ?.

Отметим некоторые свойства пирамидальной сортировки. Метод пирамидальной сортировки неустойчив и не зависит от исходной отсортированности массива

Похожие статьи




ОСНОВНЫЕ ИДЕИ И ХАРАКТЕРИСТИКИ ПРИМЕНЯЕМЫХ, МЕТОД СОРТИРОВКИ - Структуры и алгоритмы обработки данных

Предыдущая | Следующая