Структуры данных и модели вычислений



         

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


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

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

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

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

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

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

Упражнения

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

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

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




Содержание  Назад  Вперед