Алгоритм УлПир

Пример результата просеивания

Возьмем массив [1,7,5,4,9,8,12,11,2,10,3,6] (N = 12).

Его исходное состояние таково (серым цветом выделено "основание" пирамиды, не требующее просеивания):

7 5

4 9 8 12

11 2 10 3 6

После первых трех просеиваний (a[6], a[5], a[4]) получим такую картину (здесь и далее серым цветом выделяем участников просеивания):

7 5

4 9 8 12

11 2 10 3 6

7 5

11 10 9 8 12

11 2 9 10 3 6

7 5

11 4 10 8 12

4 11 2 9 3 6

Просеивание двух следующих элементов (a[3] и a[2]) тоже не вызовет вопросов - для каждого из них будет достаточно только одного шага:

7 12 5

11 10 8 5 12

4 2 9 3 6

11 7 5

7 11 10 8 12

4 2 9 3 6

А вот для просеивания последнего элемента (a[1]) понадобится целых три шага:

12 1

11 1 12

7 1 10 8 5

4 2 9 3 6

11 8 1

7 10 1 8 5

4 2 9 3 6

11 8

7 10 6 1 5

4 2 9 3 1 6

Итак, мы превратили исходный массив в пирамиду: в любой тройке a[i], a[2*i] и a[2*i+1] максимум находится "сверху".

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

0-й шаг: Превратить исходный массив в пирамиду (с помощью просеивания).

1-й шаг: Для N-1 элементов, начиная с последнего, производить следующие действия:

поменять местами очередной "рабочий" элемент с первым;

просеять (новый) первый элемент, не затрагивая, однако, уже отсортированный хвост последовательности (элементы с i-го по N-й).