Сортировка с помощью d-кучи.

Для представления сортируемой последовательности используем структуру -кучи. Сортировку можно провести в два этапа.

1. Окучить сортируемый массив, применяя последовательно операцию ПОГРУЖЕНИЕ по очереди к узлам

   в предположении, что сначала все ключей занимают в произвольном порядке массив .

2. Осуществить окончательную сортировку следующим образом. Первый (минимальный) элемент кучи меняем местами с последним, уменьшаем размер кучи на 1 (минимальный элемент остается в последней позиции массива , не являясь уже элементом кучи) и применяем операцию ПОГРУЖЕНИЕ к корню, затем повторяем аналогичные действия, пока размер кучи не станет равным 1.

Эти два этапа реализуются с помощью процедуры SORT, которая сортирует массив по убыванию ключей:

Заметим, что процедура не требует дополнительной памяти, размер которой зависел бы от длины массива .

Упражнения

1. Докажите, что оператор

   в процедуре можно заменить оператором

2. Напишите программу сортировки числового массива с помощью процедуры и испытайте ее на массивах, сгенерированных с помощью датчика случайных чисел. Составьте таблицу, отражающую время работы вашей программы на массивах разной длины. Каков максимальный размер массива, который можно отсортировать составленной программой на вашем компьютере?

Содержание раздела

---