Стр. 99 - Основы алгоритмов и структур данных

Содержание 97
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
5.5.2. Естественное слияние
В случае простого слияния мы ничего не выигрываем, если данные уже
частично рассортированы. На k – м проходе длина всех сливаемых
подпоследовательностей меньше или равна 2k без учета того, что более
длинные подпоследовательности уже могут быть упорядочены и их можно
было бы сливать. Фактически можно было бы сразу сливать какие – либо
упорядоченные подпоследовательности длиной m и n в одну
последовательность из m + n элементов. Метод сортировки, при котором
каждый раз сливаются две самые длинные возможные подпоследовательности,
называется естественным слиянием. Упорядоченную подпоследовательность
часто называют цепочкой. Но, поскольку слово “цепочка” чаще используется
для обозначения последовательности символов, то будем использовать слово
серия, когда речь идет об упорядоченной подпоследовательности. Назовём
подпоследовательность а i ..., аj , такую, что:
1 + ≤ k k a a, для 1 ,..., − = j i k .
i i a a >
−1 ,
1 + > j j a a
максимальной серией или серией. Итак, сортировка естественным слиянием
сливает не последовательности фиксированной, заранее заданной длины, а
(максимальные) серии. Серии имеют то свойство, что при слиянии двух
последовательностей, каждая из которых содержит n серий, возникает одна
последовательность, содержащая ровно n серий. Таким образом, на каждом
проходе общее число серий уменьшается вдвое, а число необходимых
пересылок элементов в худшем случае равно n [log2n], а в обычном случае даже
меньше. Ожидаемое число сравнений, однако, намного больше. Так как, кроме
сравнений, необходимых для упорядочения элементов, требуются еще
сравнения соседних элементов каждого файла для определения концов серии.
5.5.3. Частичная сортировка
Раньше мы изучали проблему полного упорядочения множества имен, не
имея a priori информации об абстрактном порядке имен. Теперь вместо полного
упорядочения требуется только определить k-е наибольшее имя (т.е. k – е имя в
порядке убывания)
Задача нахождения k -го из наибольших в порядке убывания при данных
именах х1, х 2, ..., хn , очевидно, симметрична: отыскание (n – k – 1)-го
наибольшего (k – го наименьшего) имени можно осуществить, используя
алгоритм отыскания k – го наибольшего, но меняя местами действия,
предпринимаемые при результатах < и > сравнений имен. Таким образом,
отыскание наибольшего имени (k =1) эквивалентно отысканию наименьшего