Computing and ranking measures of presortedness

References

• Altman , T. and Chlebus , B. S. 1989/90 . Soring roughly sorted sequences in parallel . Information Processing Letters , 33 : 297 – 300 .
   Google Scholar
• Brandstädt , A. and Kratsch , D. 1986 . On partitions of permutations into increasing and decreasing subsequences . Journal of Information Processing and Cybernetics , 22 : 263 – 273 .
   Google Scholar
• Chen , J. and Carlsson , S. 1990 . Fifth SIAM Conference on Discrete Mathematics . Measuring presortedness and evaluating disorder . 1990 , GA, USA.
   Google Scholar
• Chen , J. and Carlsson , S. 1991 . Second Annual ACM-SIAM Symposium on Discrete Algorithms . On partitions and presortedness of sequences . 1991 , CA, USA. pp. 62 – 71 .
   Google Scholar
• Cook , C. R. and Kim , D. J. 1980 . Best sorting algorithm for nearly sorted lists . Communications of the ACM , 23 620 – 624 .
   Google Scholar
• Diaconis , P. and Graham , R. L. 1977 . Spearman's footrule as a measure of disarray . Journal of the Royal Statistical Society , B 39 262 – 268 .
   Google Scholar
• Dijkstra , E. W. 1982 . Smoothsort, an alternative for sorting in situ . Science of Computer Programming , 1 223 – 233 .
   Google Scholar
• Dilworth , R. P. 1950 . A decomposition theorem for partially ordered sets . Annals of Mathematics , 51 161 – 166 .
   Web of Science ®Google Scholar
• Estivill-Castro , V. and Wood , D. 1989 . A new measure of presortedness . Information and Computation , 83 111 – 119 .
   Google Scholar
• Fredman , M. L. 1976 . How good is the information theory bound in sorting? . Theoretical Computer Science , 1 355 – 361 .
   Google Scholar
• Fredman , M. L. 1975 . On computing the length of longest increasing subsequences . Discrete Mathematics , 11 29 – 35 .
   Web of Science ®Google Scholar
• Johnson , D. S. 1974 . Approximation algorithms for combinatorial problems . Journal of Computer and System Sciences , 9 256 – 278 .
   Web of Science ®Google Scholar
• Knuth , D. E. 1973 . The Art of Computer Programming, Sorting and Searching , Vol. 3 , Reading, MA : Addison-Wesley .
   Google Scholar
• Mannila , H. 1985 . Measures of presortedness and optimal sorting algorithms . IEEE Transactions on Computers , C 34 : 318 – 325 .
   Google Scholar
• Mehlhorn , K. 1979 . Theoretical Computer Science. Proceedings of the 4th GI Conference on Theoretical Computer Science . Sorting presorted files . 1979 . pp. 199 – 212 . In: Weihrauch, K. (ed.) Aachen
   Google Scholar
• Moffat A. Ranking measures of sortedness and sorting nearly sorted lists Department of Computer Science, The University of Melbourne Australia July 1990 Technical Report 90/9
   Google Scholar
• Petersson O. Adaptive sorting Lund University Sweden December 1990 Ph. D. Thesis
   Google Scholar
• Skiena , S. S. 1988 . Encroaching lists as a measure of presortedness . BIT , 28 775 – 784 .
   Google Scholar
• Wagner , K. 1984 . Monotonie coverings of finite sets . Journal of Information Processing and Cybernetics , 20 633 – 639 .
   Google Scholar