Структуры данных и модели вычислений
Сортировка методом "разделяй и властвуй".
Предположим, что в нашем распоряжении имеется процедура РАЗДЕЛЯЙ , которая по заданным значениям индексов , находит некоторое промежуточное значение и переставляет элементы сегмента так, чтобы для
выполнялось неравенство , а для — неравенство .
Тогда для сортировки сегмента
может быть использована рекурсивная процедура СОРТИРУЙ.
Для сортировки всего исходного массива достаточно выполнить оператор СОРТИРУЙ .
Заметим, что если бы процедура РАЗДЕЛЯЙ работала линейное от длины сегмента время и давала значение , близкое к середине между
и , то число обращений к ней приблизительно равнялось бы и сортировка всего массива проходила бы за время порядка . Однако можно доказать, что при естественной реализации эта оценка справедлива лишь в среднем.
Упражнения
- Разработайте вариант процедуры СОРТИРУЙ без использования рекурсии. Сколько дополнительной памяти требуется для запоминания границ еще не отсортированных сегментов?
- Охарактеризуйте работу процедуры СОРТИРУЙ на заранее отсортированном массиве.
- Напишите на известном вам алгоритмическом языке программу сортировки числового массива с помощью процедуры СОРТИРУЙ и испытайте ее на массивах, сгенерированных с помощью датчика случайных чисел.
- Составьте таблицу, отражающую время работы вашей программы на массивах разной длины. Каков максимальный размер массива, который можно отсортировать составленной программой на вашем компьютере?
