On extremal sort sequences

A sort sequence S_n is a sequence of all unordered pairs of indices inI _n = {1, 2, ..., n}. With a sort sequenceS_n = (s₁ ,s₂ ,...,s_{( 2ⁿ )} )S_n = (s_1 ,s_2 ,...,s_{\left( {_2^n } \right)} ), one can associate a predictive sorting algorithm A(S_n). An execution of the algorithm performs pairwise comparisons of elements in the input setX in the order defined by the sort sequence S_n except that the comparisons whose outcomes can be inferred from the results of the preceding comparisons are not performed. A sort sequence is said to be extremal if it maximizes a given objective function. First we consider the extremal sort sequences with respect to the objective function ω(S_n) — the expected number of active predictions inS _n. We study ω-extremal sort sequences in terms of their prediction vectors. Then we consider the objective function Ω(S_n) — the minimum number of active predictions in S_n over all input orderings.     

The characterization of sort sequences

A sort sequenceS _n is a sequence of all unordered pairs of indices inI _n = 1, 2, ...,n. With a sort sequenceS _n, we associate a sorting algorithmA(S _n) to sort input setX = x ₁, x₂, ..., x_n as follows. An execution of the algorithm performs pairwise comparisons of elements in the input setX as defined by the sort sequenceS _n, except that the comparisons whose outcomes can be inferred from the outcomes of the previous comparisons are not performed. Let χ(S _n) denote the average number of comparisons required by the algorithmA(S _n assuming all input orderings are equally likely. Let χ*(n) and χ°(n) denote the minimum and maximum values, respectively, of χ(S _n) over all sort sequencesS _n. Exact determination of χ*(n), χO(n) and associated extremal sort sequences seems difficult. Here, we obtain bounds on χ*(n) and χO(n).     

Sorting under partial information (without the ellipsoid algorithm)

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (J. Comput. System Sci. 51 (3), 390–399, 1995) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once, in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present:

1. an O(n ²) algorithm performing O(logn·log e(P)) comparisons
2. an O(n ^2:5) algorithm performing at most (1+?) log e(P)+O _? (n) comparisons
3. an O(n ^2:5) algorithm performing O(log e(P)) comparisons.

All our algorithms can be implemented in such a way that their computational bottleneck is confined in a preprocessing phase, while the sorting phase is completed in O(q)+O(n) time, where q denotes the number of comparisons performed.     

A Note on Average-Case Sorting

This note studies the average-case comparison-complexity of sorting n elements when there is a known distribution on inputs and the goal is to minimize the expected number of comparisons. We generalize Fredman’s algorithm which is a variant of insertion sort and provide a basically tight upper bound: If μ is a distribution on permutations on n elements, then one may sort inputs from μ with expected number of comparisons that is at most H(μ) + 2n, where H is the entropy function. The algorithm uses less comparisons for more probable inputs: For every permutation π, the algorithm sorts π by using at most \(\log _{2}(\frac {1}{\Pr _{\mu }(\pi )})+2n\) comparisons. A lower bound on the expected number of comparisons of H(μ) always holds, and a linear dependence on n is also required.     

Quadripartite Sort

This paper presents an efficient and practical sorting algorithm, called Quadripartite Sort. It lies between MergeSort and QuickSort. This algorithm sortsnelements using bounded workspace andn log n + 1.75ncomparisons in the worst case. By empirical testing, we conjecture that this algorithm needs approximatelyn log n − ncomparisons on average. When usingm-way merging strategy, wheremis a larger constant, this algorithm becomes an in-place sorting algorithm whose comparison plus exchange total is absolutely minimum among known constant workspace algorithms. For example, using a 256-way merging, the comparison plus exchange total required is approximately 1.2495n log n + O(n) in the worst case.     

Stable in situ sorting and minimum data movement

In this paper, we describe an algorithm to stably sort an array ofn elements using only a linear number of data movements and constant extra space, albeit in quadratic time. It was not known previously whether such an algorithm existed. When the input contains only a constant number of distinct values, we present a sequence ofin situ stable sorting algorithms makingO(n lg^(k+1) n+kn) comparisons (lg^(K) means lg iteratedk times and lg* the number of times the logarithm must be taken to give a result 0) andO(kn) data movements for any fixed valuek, culminating in one that makesO(n lg*n) comparisons and data movements. Stable versions of quicksort follow from these algorithms.Research supported by Natural Sciences and Engineering Research Council of Canada grant No.A-8237 and the Information Technology Research Centre of Ontario.Supported in part by a Research Initiation Grant from the Virginia Engineering Foundation.     

On the Skeleton of the Polytope of Pyramidal Tours

We consider the skeleton of the polytope of pyramidal tours. A Hamiltonian tour is called pyramidal if the salesperson starts in city 1, then visits some cities in increasing order of their numbers, reaches city n, and returns to city 1 visiting the remaining cities in decreasing order. The polytope PYR(n) is defined as the convex hull of the characteristic vectors of all pyramidal tours in the complete graph K _n . The skeleton of PYR(n) is the graph whose vertex set is the vertex set of PYR(n) and the edge set is the set of geometric edges or one-dimensional faces of PYR(n). We describe the necessary and sufficient condition for the adjacency of vertices of the polytope PYR(n). On this basis we developed an algorithm to check the vertex adjacency with linear complexity. We establish that the diameter of the skeleton of PYR(n) equals 2, and the asymptotically exact estimate of the clique number of the skeleton of PYR(n) is Θ(n²). It is known that this value characterizes the time complexity in a broad class of algorithms based on linear comparisons.     

An analysis of (h,k, 1)-Shellsort

One classical sorting algorithm, whose performance in many cases remains unanalyzed, is Shellsort. Let h be a t-component vector of positive integers. An h-Shellsort will sort any given n elements in t passes, by means of comparisons and exchanges of elements. Let S>_j(h; n) denote the average number of element exchanges in the jth pass, assuming that all the n! initial orderings are equally likely. In this paper we derive asymptotic formulas of S_j(h; n) for any fixed h = (h, k, l), making use of a new combinatorial interpretation of S₃. For the special case h = (3, 2, 1), the analysis is further sharpened to yield exact expressions.     

Finding the maximum and minimum elements with one lie

In this paper we deal with the problem of finding the smallest and the largest elements of a totally ordered set of size n using pairwise comparisons if one of the comparisons might be erroneous and prove a conjecture of Aigner stating that the minimum number of comparisons needed is for some constant c. We also address some related problems.     

Stable minimum space partitioning in linear time

In the stable0–1 sorting problem the task is to sort an array ofn elements with two distinct values such that equal elements retain their relative input order. Recently, Munro, Raman and Salowe gave an algorithm which solves this problem inO(n log*n) time and constant extra space. We show that by a modification of their method the stable0–1 sorting is possible inO(n) time andO(1) extra space. Stable three-way partitioning can be reduced to stable0–1 sorting. This immediately yields a stable minimum space quicksort, which sorts multisets in asymptotically optimal time with high probability.     

Sorting and generating reduced words

We introduce a partial order on the set of all reduced words of a given permutation ω, called directed-braid poset of ω. This poset enables us to produce two algorithms: One is a sorting algorithm applied to any reduced word of ω and aims to obtain the natural word (i.e. lexicographically largest reduced word); the other one is a generation algorithm applied to the natural word and returns the set of all reduced words of ω.     

Sorting with networks of data structures

We consider the problem of sorting a permutation using a network of data structures as introduced by Knuth and Tarjan. In general the model as considered previously was restricted to networks that are directed acyclic graphs (DAGs) of stacks and/or queues. In this paper we study the question of which are the smallest general graphs that can sort an arbitrary permutation and what is their efficiency. We show that certain two-node graphs can sort in time Θ(n²) and no simpler graph can sort all permutations. We then show that certain three-node graphs sort in time Ω(n^3/2), and that there exist graphs of k nodes which can sort in time Θ(nlog_kn), which is optimal.     

On sorting by 3-bounded transpositions

Heath and Vergara [Sorting by short block moves, Algorithmica 28 (2000) 323-352] proved the equivalence between sorting by 3-bounded transpositions and sorting by correcting skips and correcting hops. This paper explores various algorithmic as well as combinatorial aspects of correcting skips/hops, with the aim of understanding 3-bounded transpositions better.We show that to sort any permutation via correcting hops and skips, ⌊n/2⌋ correcting skips suffice. We also present a tighter analysis of the approximation algorithm of Heath and Vergara, and a possible simplification. Along the way, we study the class H_n of those permutations of S_n which can be sorted using correcting hops alone, and characterize large subsets of this class. We obtain a combinatorial characterization of the set G_n⊆S_n of all correcting-hop-free permutations, and describe a linear-time algorithm to optimally sort such permutations. We also show how to efficiently sort a permutation with a minimum number of correcting moves.     

On n-hamiltonian graphs

A graph G of order p ? 3 is called n-hamiltonian, 0 ? n ? p ? 3, if the removal of any m vertices, 0 ? m ? n, results in a hamiltonian graph. A graph G of order p ? 3 is defined to be n-hamiltonian, ?p ? n ? 1, if there exists ?n or fewer pairwise disjoint paths in G which collectively span G. Various conditions in terms of n and the degrees of the vertices of a graph are shown to be sufficient for the graph to be n-hamiltonian for all possible values of n. It is also shown that if G is a graph of order p ? 3 and $\text{K}\text{(G) ? β(G) + n (?p ? n ? p ? 3)}$, then G is n-hamiltonian.     

Separation of clones of cooperations by cohyperidentities

An n-ary cooperation is a mapping from a nonempty set A to the nth copower of A. A clone of cooperations is a set of cooperations which is closed under superposition and contains all injections. Coalgebras are pairs consisting of a set and a set of cooperations defined on this set. We define terms for coalgebras, coidentities and cohyperidentities. These concepts will be applied to give a new solution of the completeness problem for clones of cooperations defined on a two-element set and to separate clones of cooperations by coidentities.     

Efficient algorithms for merging

Efficient algorithms are given to find the maximum lengthn of an ordered list in which 4 elements can be merged using exactlyk comparisons. A top down algorithm for the (2,n) merge problem is discussed and is shown to obtain the optimal merge length first reported by Hwang and Lin. Our algorithms combine this top down approach and strong heuristics, some of which derived from Hwang's optimal algorithm for the (3,n) problem, and produce a lengthn which is close to the optimal lengthf ₄(k).     

On computing the length of longest increasing subsequences

Let S = x₁, x₂, … x_n be a sequence of n distinct elements from a linearly ordered set. We consider the problem of determining the length of the longest increasing subsequences of S. An algorithm which performs this task is described and is shown to perform n log n?n log log n + O(n) comparisons in its worst case. This worst case behavior is shown to be best possible.     

A diophantine problem concerning cubes

This paper deals with the problem of finding n integers such that their pairwise sums are cubes. We obtain eight integers, expressed in parametric terms, such that all the six pairwise sums of four of these integers are cubes, 9 of the 10 pairwise sums of five of these integers are cubes, 12 pairwise sums of six of these integers are cubes, 15 pairwise sums of seven of these integers are cubes and 18 pairwise sums of all the eight integers are cubes. This leads to infinitely many examples of four positive integers such that all of their six pairwise sums are cubes. Further, for any arbitrary positive integer n, we obtain a set of 2(n+1) integers, in parametric terms, such that 5n+1 of the pairwise sums of these integers are cubes. With a choice of parameters, we can obtain examples with 5n+2 of the pairwise sums being cubes.     

Solving covering problems and the uncapacitated plant location problem on trees

Given a tree network on n vertices, a neighborhood subtree is defined as the set of all points on the tree within a certain radius of a given point, called the center. It is shown that for any two neighborhood subtrees containing the same endpoint of a longest path in the tree one is contained in the other. This result is then used to obtain O(n²) algorithms for the minimum cost covering problem and the minimum cost operating problem as well as an O(n³) algorithm for the uncapacitated plant location problem on the tree.     

Robust ordinal regression for value functions handling interacting criteria

We present a new method called UTA^GMS–INT for ranking a finite set of alternatives evaluated on multiple criteria. It belongs to the family of Robust Ordinal Regression (ROR) methods which build a set of preference models compatible with preference information elicited by the Decision Maker (DM). The preference model used by UTA^GMS–INT is a general additive value function augmented by two types of components corresponding to “bonus” or “penalty” values for positively or negatively interacting pairs of criteria, respectively. When calculating value of a particular alternative, a bonus is added to the additive component of the value function if a given pair of criteria is in a positive synergy for performances of this alternative on the two criteria. Similarly, a penalty is subtracted from the additive component of the value function if a given pair of criteria is in a negative synergy for performances of the considered alternative on the two criteria. The preference information elicited by the DM is composed of pairwise comparisons of some reference alternatives, as well as of comparisons of some pairs of reference alternatives with respect to intensity of preference, either comprehensively or on a particular criterion. In UTA^GMS–INT, ROR starts with identification of pairs of interacting criteria for given preference information by solving a mixed-integer linear program. Once the interacting pairs are validated by the DM, ROR continues calculations with the whole set of compatible value functions handling the interacting criteria, to get necessary and possible preference relations in the considered set of alternatives. A single representative value function can be calculated to attribute specific scores to alternatives. It also gives values to bonuses and penalties. UTA^GMS–INT handles quite general interactions among criteria and provides an interesting alternative to the Choquet integral.