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

From

Ruslan Shevelyov (2:5020/9481.21)

To

Dmitry Kalmikov

Date

2002-09-20T23:14:20Z

Area

RU.ALGORITHMS

Здравствуйте, Dmitry.


DK> Кто нибудь алгоритм сабжа расталкует ?

Надо же! Не все ещё забыли мой любимый метод ;-))

Сначала дадим определение пирамиды:
DEF: Последовательность h[L], h[L+1], ..., h[R-1], h[R]
называется пирамидой, если для любого i: L<=i<=R, 2*i<=R
выполняются неравенства h[i]<=h[2*i] и, если 2*i<R,
h[i]<=h[2*i+1].

Нетрудно заметить, что:
1. Если 2*L>R, то последовательность h[L]...h[R] образует
пирамиду независимо от значений элементов последовательности;
2. Если L=1, то наименьший элемент последовательности -- это h[1];
3. Если h[L]...h[R] -- пирамида, то h[L]...h[R-1] и h[L+1]...h[R] 
-- тоже пирамиды;
4. Если h[L]...h[R] -- пирамида, то за O(log(R-L)) шагов её можно
расширить на 1 элемент влево с помощью процедуры просеивания,
которая состоит в следующем:

Пусть надо просеять через пирамиду h[L]...h[R] элемент h[L-1].
Выберем среди элементов h[L-1], h[2*(L-1)], h[2*(L-1)+1]
наименьший. Если это h[L-1], то просеивание закончено,
h[L-1]...h[R] -- пирамида. Иначе поменяем местами этот
элемент (обозначим его индекс j) и h[L-1] и просеем h[j]
через пирамиду h[j+1]...h[R] (Цикл заканчивается при
h[2*j]>R).

И, наконец, собственно алгоритм. Пусть надо отсортировать
массив h[1]...h[N].

Шаг 0. Преобразуем массив в пирамиду:
h[(N div 2)+1]...h[N] -- это пирамида.
Теперь в цикле for x=(N div 2) downto 1 просеиваем элемент
h[x] через пирамиду h[x+1]...h[N].

Шаг 1. Построение массива, отсортированного в порядке убывания.
В цикле for x=N downto 2 do begin
  h[1]...h[x-1] -- пирамида; наименьший её элемент -- h[1].
  Поменяем местами h[1] и h[x].
  Просеем (новый) h[1] через пирамиду h[2]...h[x-1].
end;

Шаг 2. Теперь элементы массива упорядочены (в порядке убывания).
Осталось только инвертировать массив.

Вот, собственно, и всё.

WBR...

---
 * Origin: Cosmo Canyon Station (2:5020/9481.21)