Оценка сложности алгоритма сортировки железнодорожного состава

Аннотация

Рассматривается задача сортировки грузового железнодорожного состава и ее математическая формулировка. Описывается предлагаемый алгоритм, использующий сортировочную горку. Эта горка состоит из небольшого возвышения, с которого спускается дерево путей, начинающихся на верхушке холма и разделяющихся на k путей, с возможностью провести вагон с верхушки возвышения в любой заданный конец. На каждом прогоне вагоны распределяются по путям, а затем состав собирается из получившихся фрагментов. Находятся максимальное число прогонов всего поезда через горку для сортировки состава и общая трудоемкость алгоритма. Некоторыми чертами идея этого метода похожа на основную идею алгоритма сортировки перфокарт в классическом счетно-аналитическом комплекте. Исходные данные - это перестановка, сопоставляющая каждому вагону его номер от конца в требуемом расположении вагонов. В решении используется разбиение перестановки 1: n на монотонные сегменты. Например, перестановка 3,8,2,6,1,4,5,7 с n = 8 разбивается на сегменты (3,2,1), (4), (6,5), (8,7). Эти сегменты легче определить в терминах перестановки, обратной исходной. Она считается строкой из чисел, и каждому сегменту разбиения исходной перестановки соответствует максимальная подстрока из монотонно убывающих чисел. В примере обратная перестановка 5,3,1;6;7,4;8,2 разбивается на4подстроки(разделенные знаками «;»).Пусть p-числочастей в этом разбиении, а k-число путей на горке. Доказано, что число прогонов состава через горку для получания n,n -1,..., 2,1 не превосходит ⌈log_k p⌉ ⌈log_k n⌉, и эта оценка достигается предложенным в статье алгоритмом. Библиогр. 2 назв.

Ключевые слова:

упорядочение перестановки, сортировочная горка