Programming Techniques
R. Morris Editor
A technique for proving min-max norms of sorting algorithms is given. One new algorithm for finding the minimum and maximum elements of a set with fewest comparisons is proved optimal with this technique.
Key Words and Phrases: sorting, computational complexity, computational combinatorics
CR Categories: 5.29, 5.31
A Sorting
Problem and
Its Complexity
Ira Pohl
University of California*
A sorting problem is a special case of finding a set partition. The elements are identified by their rank in a linear order. For a given finite set
X = {xl, x2,…, x,}
There is some permutation r*, such that
XTr*~l) < Xlr*~2) < . . . < XTr*~n~ .
(Note: we will ignore throughout the case of XTr*<~) =
Other partitions which do not completely sort the set are often of interest, such as finding the minimum element, the maximum element, the first K smallest elements, the median or, as will be discussed here, the minimum and maximum elements.
Algorithms which take unordered (or partially ordered) sets and produce the desired partition are fundamental to computing, making this area one of the most intensely studied both practically and theoreti- cally. In the theoretical attacks, the principal unit of work has been the comparison. An algorithm is com- pared to some norm on the number of comparisons. The two norms of most interest are the maximum and the average. The maximum norm (M-norm) is the greatest number of comparisons the algorithm takes over all possible inputs ( n !orderings are possible). The average norm (E-norm) is the average number of comparisons the algorithm takes with respect to the
uniform distribution on the possible orderings. The best algorithm for a given norm is the one that minimizes that norm.
The goals of this paper are: (1) to demonstrate a technique for proving algorithms optimal in the maxi- mum norm; and (2) using the technique developed, to exhibit a new algorithm P2 for finding both the mini- mum and maximum of a set, which is then proven optimal in the M-norm.
Copyright (~) 1972, Association for Computing Machinery, Inc.
General permission to republish, but not for profit, all or part of this material is granted, provided that reference is made to this publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Com- puting Machinery.
* Information and Computer Science Department, and Stevenson College, University of California, Santa Cruz, CA 95060. This paper is a revision of a privately distributed communi- cation, March 1970.
462
Communications of
the ACM
June 1972 Volume 15 Number 6
A well-known result [1] is that n - 1 comparisons is M-optimal for finding the minimum (or maximum) element of an unordered set. (It is also E-optimal.)
Algorithm P1
rain := xl;
fori:= 2step1untilndo
rnm := if rain