Структуры данных и модели вычислений
Сортировка с помощью d-кучи.
Для представления сортируемой последовательности используем структуру -кучи. Сортировку можно провести в два этапа.
- Окучить сортируемый массив, применяя последовательно операцию ПОГРУЖЕНИЕ по очереди к узлам
в предположении, что сначала все ключей занимают в произвольном порядке массив .
- Осуществить окончательную сортировку следующим образом. Первый (минимальный) элемент кучи меняем местами с последним, уменьшаем размер кучи на 1 (минимальный элемент остается в последней позиции массива , не являясь уже элементом кучи) и применяем операцию ПОГРУЖЕНИЕ к корню, затем повторяем аналогичные действия, пока размер кучи не станет равным 1.
Эти два этапа реализуются с помощью процедуры SORT, которая сортирует массив по убыванию ключей:
Заметим, что процедура не требует дополнительной памяти, размер которой зависел бы от длины массива .
Упражнения
- Докажите, что оператор
в процедуре можно заменить оператором
- Напишите программу сортировки числового массива с помощью процедуры и испытайте ее на массивах, сгенерированных с помощью датчика случайных чисел. Составьте таблицу, отражающую время работы вашей программы на массивах разной длины. Каков максимальный размер массива, который можно отсортировать составленной программой на вашем компьютере?
