Abstract
The purpose of this paper is to consider a special kind of sorting problem in which a sequencea 1 ...a n is to be rearranged into an optimal order by interchanging pairs of adjacent elements, where certain pairs of elements are not allowed to commute with each other. Section 1 presents an informal example intended to clarify the nature of the problem, while Secs. 2 and 3 give some formal definitions and characterizations. Section 4 shows that the problem we are considering is equivalent to finding the lexicographically smallest topological sorting in a partial order.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anatoly V. Anisimov, “Inhomogeneous Insertion Sorting,” in preparation.
Donald E. Knuth, “The Art of Computer Programming,” Vol. 1,Fundamental Algorithms (Addison-Wesley, Reading, Massachusetts, 1969).
Donald E. Knuth, “The Art of Computer Programming,” Vol. 3,Sorting and Searching (Addison-Wesley, Reading, Massachusetts, 1973).
Author information
Authors and Affiliations
Additional information
The work of this author was performed while visiting Stanford University, with the support of the International Research and Exchanges Board (IREX).
Rights and permissions
About this article
Cite this article
Anisimov, A.V., Knuth, D.E. Inhomogeneous sorting. International Journal of Computer and Information Sciences 8, 255–260 (1979). https://doi.org/10.1007/BF00993053
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00993053