Measures of Presortedness and Optimal Sorting Algorithms
- 1 April 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (4) , 318-325
- https://doi.org/10.1109/tc.1985.5009382
Abstract
The concept of presortedness and its use in sorting are studied. Natural ways to measure presortedness are given and some general properties necessary for a measure are proposed. A concept of a sorting algorithm optimal with respect to a measure of presortedness is defined, and examples of such algorithms are given. A new insertion sort algorithm is shown to be optimal with respect to three natural measures. The problem of finding an optimal algorithm for an arbitrary measure is studied, and partial results are proven.Keywords
This publication has 17 references indexed in Scilit:
- Smoothsort's behavior on presorted sequencesInformation Processing Letters, 1983
- A new data structure for representing sorted listsActa Informatica, 1982
- Smoothsort, an alternative for sorting in situScience of Computer Programming, 1982
- Some modified algorithms for Dijkstra's longest upsequence problemActa Informatica, 1982
- Localized search in sorted listsPublished by Association for Computing Machinery (ACM) ,1981
- Best sorting algorithm for nearly sorted listsCommunications of the ACM, 1980
- A new representation for linear listsPublished by Association for Computing Machinery (ACM) ,1977
- How good is the information theory bound in sorting?Theoretical Computer Science, 1976
- Sorting X + YCommunications of the ACM, 1975
- Two applications of a probabilistic search techniquePublished by Association for Computing Machinery (ACM) ,1975