Рассматриваемые здесь задачи можно отнести
Рассматриваемые здесь задачи можно отнести к наиболее часто встречающимся классам комбинаторных задач. Почти во всех машинных приложениях множество объектов должно быть переразмещено в соответствии с некоторым заранее определенным порядком. Например, при обработке коммерческих данных часто бывает необходимо расположить их по алфавиту или по возрастанию номеров. В числовых расчетах иногда требуется знать наибольший корень многочлена, и т.д.
Будем считать заданной таблицу с
именами, обозначаемыми
,
. Каждое имя
принимает значение из пространства имен, на котором определен линейный порядок. Будем считать, что никакие два имени не имеют одинаковых значений; то есть любые
обладают тем свойством, что если
, то либо
, либо
. Ограничение
при
упрощает анализ без потери общности, ибо и при наличии равных имен корректность идей и алгоритмов не нарушается. Наша цель состоит в том, чтобы выяснить что- нибудь относительно перестановки
для которой
. В задаче полной сортировки требуется полностью определить
, хотя обычно это делается неявно путем переразмещения имени в порядке возрастания. В задачах частичной сортировки требуется либо извлечь частичную информацию о
(например,
для нескольких значений
), либо полностью определить
по некоторой заданной частичной информации о ней (так обстоит дело при слиянии двух упорядоченных таблиц).
При внутренней сортировке решается задача полной сортировки для случая достаточно малой таблицы, умещающейся непосредственно в адресной памяти. Внешняя сортировка представляет собой задачу полной сортировки для случая такой большой таблицы, что доступ к ней организован по частям, расположенным на внешних запоминающих устройствах. Частичная сортировка - задачи выбора
- наибольшего имени и слияния двух упорядоченных таблиц.
Содержание раздела
