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



             

Частичная сортировка (слияние)


Вторым направлением исследования частичной сортировки является задача слияния двух отсортированных таблиц

x_1 \leqslant x_2 \leqslant \ldots \leqslant x_n
и
y_1 \leqslant y_2 \ldots \leqslant y_m

в одну отсортированную таблицу

z_1 \leqslant z_2 \leqslant \ldots \leqslant z_{n + m}
. Существует очевидный способ это сделать: таблицы, подлежащие слиянию, просматривать параллельно, выбирая на каждом шаге меньшее из двух имен и помещая его в окончательную таблицу. Этот процесс немного упрощается добавлением имен-сторожей
x_{n + 1} = y_{m + 1} = \infty
, как в алгоритме 15.5. В этом алгоритме
i
и
j
указывают, соответственно, на последние имена в двух входных таблицах, которые еще не были помещены в окончательную таблицу.

Алгоритм 15.5. Прямое слияние

Алгоритм 15.5. Прямое слияние




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