Методы программирования. Громов Ю.Ю - 82 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

82
Эта простая процедура, по существу, «наилучший из возможных»
способов слияния на традиционной ЭВМ при условии, что m ≈ n. Но, ес-
ли m гораздо меньше n, можно разработать более эффективные алгорит-
мы сортировки, хотя в общем случае они довольно сложны. Алгоритм М
без особой потери эффективности можно немного упростить, добавив в
конец исходных файлов искусственных «стражей» x
m+1
= y
n+1
= ∞, и оста-
навливаться перед выводом ∞.
Общий объём работы, выполняемой алгоритмом М, по существу,
пропорционален m + n.
Понятно, что слияние является более простой задачей по сравнению
с сортировкой. Однако задачу сортировки можно свести к слияниям, сли-
вая все более длинные подфайлы до тех пор, пока не будет отсортирован
весь файл. Такой подход можно рассматривать как развитие идеи сорти-
ровки вставками, так как вставка нового элемента в упорядоченный файл
является частным случаем слияния при n = 1.
С исторической точки зрения метод слияний это один из самых пер-
вых методов, предназначенных для решения задачи сортировки на ЭВМ;
он был предложен Джоном фон Нейманом ещё в 1945 г.
Слияния более подробно будут рассмотрены в связи с алгоритмами
внешней сортировки, а здесь сосредоточим своё внимание на сортировке
в быстрой памяти с произвольным доступом.
Таблица 1 иллюстрирует сортировку слиянием, когда «свечка сжи-
гается с обоих концов», подобно тем процедурам просмотра элементов
файла, которые применялись при быстрой сортировке, поразрядной об-
менной сортировке и т.д. В ней исходный файл анализируется слева и
справа в направлении к его середине. Процесс слияния имеет смысл опи-
сать на примере перехода от второй строки к третьей. Во второй строке
слева имеет место возрастающий отрезок 503 703 765, а справа, если чи-
тать справа налево, – возрастающий отрезок 87 512 677. Слияние этих
двух последовательностей даёт подфайл 87 503 512 677 703 765, который
помещается слева в третью строку. Затем возрастающая последователь-
ность ключей 61 612 908 второй строки сливается с последовательностью
ключей 170 509 897 этой же строки, и результат (61 170 509 612 897 908)
записывается справа в третью строку. Наконец, последовательность
154 275 426 653 сливается с ключом 653 (при этом перекрытие ключей не
приводит к вредным последствиям), и результат записывается слева.
Аналогичным образом вторая строка получилась из первой, четвёртая –
из третьей и пятая из четвёртой.
Вертикальными линиями в табл. 1 отмечены границы между отрез-
ками. Это так называемые ступеньки вниз, где меньший элемент следует
за большим. В середине файла обычно возникает двусмысленная ситуа-
ция, когда при движении с обоих концов прочитывается один и тот же
ключ, однако в представленном ниже алгоритме это не приводит к ос-

Страницы