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

         

Сортировка "слиянием".


Этот метод является разновидностью метода "разделяй и властвуй"; впрочем, уместнее было бы назвать его "властвуй и объединяй".

Предположим, что у нас есть процедура СЛИВАЙ (, которая два уже отсортированных сегмента и

преобразует (сливает) в один сегмент , делая его полностью отсортированным. Тогда рекурсивная процедура

очевидно, сортирует сегмент , а для сортировки всего исходного массива достаточно выполнить оператор СОРТИРУЙ . Как видим, вопрос балансировки размера сегментов решается здесь просто. Число обращений к процедуре СЛИВАЙ

равно , а время ее выполнения легко сделать линейным от суммарной длины сливаемых сегментов.

Упражнения

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



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