Complexity of a car sorting algorithm

Abstract

In this article a problem of sorting cars in a freight train is considered and its mathematical formulation is given. The sorting is executed on a so called sorting yard hump. The yard hump consists of a small hump with a tree of railroads starting on the top of the hump and branching out to k rail ends with controls that allow to direct a car moving from the top to a given end. On each run, the train is distributed to the end paths and after that collected back from fragments on the paths. The maximum number of runs of the whole train to sort it and overall complexity of the algorithm are found. Some features of this method are similar to the main idea of the well know procedure of sorting perfocards in the classical Hollerith set of hardware. The initial data is a permutation of the set 1 : n, where each car is associated with its position in the desired train sequence. In solution we use a partition of the permutation of 1 : n to monotone segments. For example, the permutation 3, 8, 2, 6, 1, 4, 5, 7 with n = 8 is divided to segments (3, 2, 1), (4), (6, 5), (8, 7). These segments are easier defined in terms of the permutation inverse to the given one. It is treated as a string consisting of numbers, and each part of the partition corresponds to a maximal monotonically decreasing set of numbers in the list of elements. In our example the inverse permutation 5, 3, 1; 6; 7, 4; 8, 2 is divided to 4 substrings by separators “;”. Let p be the number of parts in this partition, and k is the number of roads in the hump. Then the number of runs of the train through the hump to get n, n − 1, . . . , 2, 1 does not exceed ⌈log_k p⌉ 6 ⌈log_k n⌉, and this estimation is reached by the proposed algorithm. Refs 2.

Keywords:

ordering of permutation, sorting hump