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

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

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

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

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

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

Упражнения

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

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

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий