Комбинаторные алгоритмы для программистов



             

Внешняя сортировка - часть 3


Порождает ли этот выбор с замещением длинные отрезки? Ясно, что он делает это, по крайней мере, не хуже, чем очевидный метод, так как все отрезки (кроме, возможно, последнего) содержат не меньше

m
имен. На самом деле можно показать, что средняя длина отрезков, порождаемых выбором с замещением, равна
2m
, и это вполне можно считать улучшением по сравнению с очевидным методом, в котором средняя длина отрезков равна
m
. Конечно, в лучшем случае все заканчивается только одним исходным отрезком, то есть отсортированной таблицей.

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

1,2,\ldots,t

равномерно и произвести их слияние на ленту

t + 1
. Получаемые в результате отрезки снова равномерно распределить по лентам
1,2,\ldots,t
и снова произвести слияние, образуя более длинные отрезки на ленте
t + 1
. Процесс продолжается до тех пор, пока на ленте
t + 1
не останется только один отрезок (отсортированная таблица).




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