A survey of adaptive sorting algorithms
Tóm tắt
The design and analysis of adaptive sorting algorithms has made important contributions to both theory and practice. The main contributions from the theoretical point of view are: the description of the complexity of a sorting algorithm not only in terms of the size of a problem instance but also in terms of the disorder of the given problem instance; the establishment of new relationships among measures of disorder; the introduction of new sorting algorithms that take advantage of the existing order in the input sequence; and, the proofs that several of the new sorting algorithms achieve maximal (optimal) adaptivity with respect to several measures of disorder. The main contributions from the practical point of view are: the demonstration that several algorithms currently in use are adaptive; and, the development of new algorithms, similar to currently used algorithms that perform competitively on random sequences and are significantly faster on nearly sorted sequences. In this survey, we present the basic notions and concepts of adaptive sorting and the state of the art of adaptive sorting algorithms.
Từ khóa
Tài liệu tham khảo
AKL S. G. 1985. Parallel Sorting Algorithms. Academic Press Orlando. AKL S. G. 1985. Parallel Sorting Algorithms. Academic Press Orlando.
ALTO T., 1989, Roughly sorting: Sequential and parallel approach, J. Inf. Process., 12, 154
BENTLEY J. L., 1981, Proceedrags of the 19th Annual Allerton Conference on Communication, Control and Computing, 364-372
CARLSSON S., Proceedings of SIGAL lnternatmnal Symposium on Algorithms
CAYLEY A., 1849, Note on the theory of permutations. London, Edinburgh and Dubhn, Philos. Mug. J. Sc~., 34, 527
CHEN J., 1991, Proceedings of the 2nd ACM-SIAM Symposium on Discrete Algorithms. ACM, 63
DINSMORE R. J., 1965, Longer strings for sorting, Commun. ACM, 8, 1
ESTIWLL-CASTRO V. 1991. Sorting and measures of disorder. Ph.D. dissertation Univ. of Waterloo Ontari% Canada. Available as Department of Computer Science Research Report CS-91-07. ESTIWLL-CASTRO V. 1991. Sorting and measures of disorder. Ph.D. dissertation Univ. of Waterloo Ontari% Canada. Available as Department of Computer Science Research Report CS-91-07.
ESTIVILL-CASTRO V. AND WOOD D. 1991a External sorting initial runs creation and nearly sortedness. Res. Rep. CS-91-36 Dept. of Computer Science Univ. of Waterloo Ontario Canada. ESTIVILL-CASTRO V. AND WOOD D. 1991a External sorting initial runs creation and nearly sortedness. Res. Rep. CS-91-36 Dept. of Computer Science Univ. of Waterloo Ontario Canada.
ESTIVILL-CASTRO V., Advances in Cornputmg and Information Proceedzngs of the Internatwnal Conference on Computing and Informatzon
ESTIWLL-CAsTRo V. ANr~ WOOD D. t991c Randomized sorting of shuffled monotone sequences. Res Rep. CS-91-24 Dept. of Computer Science Univ. of Waterloo Ontario Canada. ESTIWLL-CAsTRo V. ANr~ WOOD D. t991c Randomized sorting of shuffled monotone sequences. Res Rep. CS-91-24 Dept. of Computer Science Univ. of Waterloo Ontario Canada.
ESTIVILL-CASTRO~ V. AND WOOD~ D. 1992b. A generic adaptive sorting algorithm. Comput. J. To be published. ESTIVILL-CASTRO~ V. AND WOOD~ D. 1992b. A generic adaptive sorting algorithm. Comput. J. To be published.
ESTWmL-CASTI~O V. AND WOOD D. 1992c. An adaptive generic sorting algorithm that uses varmble partitioning. In preparatmn. ESTWmL-CASTI~O V. AND WOOD D. 1992c. An adaptive generic sorting algorithm that uses varmble partitioning. In preparatmn.
ESTIVILL-CASTRO V. AND WOOD D. 1992d. The use of exponential search to obtain generic sorting algorithms. In preparation ESTIVILL-CASTRO V. AND WOOD D. 1992d. The use of exponential search to obtain generic sorting algorithms. In preparation
ESTIVILL-CASTRO V. MANNILA H. AND WOOD D. 1989. Right invariant metrics and measures of presortedness. D~screte Appl. Math. To be published. ESTIVILL-CASTRO V. MANNILA H. AND WOOD D. 1989. Right invariant metrics and measures of presortedness. D~screte Appl. Math. To be published.
GANNET G H. 1984. Handbook of Algorithms and Data Structures. Addison-Wesley Reading Mass GANNET G H. 1984. Handbook of Algorithms and Data Structures. Addison-Wesley Reading Mass
ISLAM T., 1990, Proceedings of the International Conference on Computing and Informatton. Canadian Scholar's Press, 81
KATAJAINEN J. AND MANNILA H. 1989. On average case optimality of a presorting algorithm. Unpublished manuscript. KATAJAINEN J. AND MANNILA H. 1989. On average case optimality of a presorting algorithm. Unpublished manuscript.
KATAJAINEN J., Proceedings o{ Optimal Algorithms
KENDALL M. G. 1970. Rank Correlatwn Methods 4th ed. Griffin London. KENDALL M. G. 1970. Rank Correlatwn Methods 4th ed. Griffin London.
KNUTH D. E. 1973. The Art of Computer Programruing. Vol. 3 Sorting and Searching. Addison- Wesley Reading Mass. KNUTH D. E. 1973. The Art of Computer Programruing. Vol. 3 Sorting and Searching. Addison- Wesley Reading Mass.
LEONG H. W. 1989. Preorder Heapsort. Tech. Rep. National Univ. of Singapore. LEONG H. W. 1989. Preorder Heapsort. Tech. Rep. National Univ. of Singapore.
LEVCOPOULOS C., Proceedings of the 8th conference on Foundations of Software Technology and Theoretical Computer Science
LEVCOPOULOS C., Proceedings of the Workshop on Algorithms and Data Structures
LEVCOPOULOS C., Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory
LEVCOPOULOS C., 1991, Proceedings of the 11th Conference on Foundations of Software Technology and Theoretical Computer Science.
LI M., 1989, A theory of learning simple concepts under simple distributions and average case complexity for the universal distribution. In Proceedings of the 30th IEEE Sympostum on Foundatwns of computer Sctence. IEEE, New York, 34, 39
MANNmA H. 1985a. Instance complexity for sorting and NP-complete problems. Ph.D. dissertation Univ. of Helsinki Dept. of Computer Science. MANNmA H. 1985a. Instance complexity for sorting and NP-complete problems. Ph.D. dissertation Univ. of Helsinki Dept. of Computer Science.
MANNILA H., 1985, Measures of presortedness and optimal sorting algorithms, IEEE Trans. Comput. C-34, 318, 325
MEHLHORN K., Proceedings of the 4th GI Conference on Theory of Computer Science
MEHLHORN K. 1984. Data Structures and Algorithms. Vol. 1 Sorting and Searching. EATCS Monographs on Theoretical Computer Science Springer-Verlag Berlin/Heidelberg. MEHLHORN K. 1984. Data Structures and Algorithms. Vol. 1 Sorting and Searching. EATCS Monographs on Theoretical Computer Science Springer-Verlag Berlin/Heidelberg.
MOFF T, A, 1991, Proceedings of the 14th Australian Computer Science Conference, 08
MOF~'AT A., 1991, the Second Annual International Symposium on Algortthms. Lecture Notes in Computer Science
MOFFAT A., Proceedings of the 3rd Scandinavian Workshop on Algorithm Theory
MOFFAT A., 1992, Proceedmgs of the 15th Austrahan Computer Science Conference, 603 613
MUNRO J. I. AND SPIRA P. M. Sorting and searching in multisets. SIAM J. Comput. 5 i (Mar.) 1976. MUNRO J. I. AND SPIRA P. M. Sorting and searching in multisets. SIAM J. Comput. 5 i (Mar.) 1976.
PAPADAKIS T., Proceedings of the 2nd Scandinavian Workshop on Algortthm Theory
PETERSSON O. 1990. Adaptive sorting. Ph.D. dissertation Lund Univ. Dept. of Computer Science. PETERSSON O. 1990. Adaptive sorting. Ph.D. dissertation Lund Univ. Dept. of Computer Science.
QUINN M. J. 1987. Designing Efficient Algorithms for Parallel Computers. McGraw-Hill New York. QUINN M. J. 1987. Designing Efficient Algorithms for Parallel Computers. McGraw-Hill New York.
SEDGEWICK a. 1980. Quzcksort. Garland Publishing New York. SEDGEWICK a. 1980. Quzcksort. Garland Publishing New York.
SLOANE N. J., Proceedings of Cryptography, Burg Feuerstein 82
YAO A. C., 1977, Proceedings of the 18th IEEE Symposium on Foundations of Computer Science, 222-227
ZHENG L.-Q AND LARSON P.-A. 1992. Speeding up external mergesort. Res. Rep. CS-92-40 Dept of Computer Science Univ of Waterloo Ontario Canada. ZHENG L.-Q AND LARSON P.-A. 1992. Speeding up external mergesort. Res. Rep. CS-92-40 Dept of Computer Science Univ of Waterloo Ontario Canada.