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

         

Сортировка методом "разделяй и властвуй".


Предположим, что в нашем распоряжении имеется процедура РАЗДЕЛЯЙ , которая по заданным значениям индексов , находит некоторое промежуточное значение и переставляет элементы сегмента так, чтобы для

выполнялось неравенство , а для — неравенство .

Тогда для сортировки сегмента

может быть использована рекурсивная процедура СОРТИРУЙ.

Для сортировки всего исходного массива достаточно выполнить оператор СОРТИРУЙ .

Заметим, что если бы процедура РАЗДЕЛЯЙ работала линейное от длины сегмента время и давала значение , близкое к середине между

и , то число обращений к ней приблизительно равнялось бы и сортировка всего массива проходила бы за время порядка . Однако можно доказать, что при естественной реализации эта оценка справедлива лишь в среднем.

Упражнения

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



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