×

Presorting algorithms: an average-case point of view. (English) Zbl 0944.68041

Summary: We introduce the concept of presorting algorithms, quantifying and evaluating the performance of such algorithms with the average reduction in number of inversions. Stages of well-known algorithms such as Shellsort and quicksort are evaluated in such a framework and shown to cause a meaning drop in the inversion statistic. The expected value, variance and generating function for the decrease in number of inversions are computed. The possibility of “presorting” a sorting algorithm is also investigated under a similar framework.

MSC:

68P10 Searching and sorting
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Burge, W. H., Sorting, trees, and measures of order, Inform. and Control, 1, 181-197 (1958) · Zbl 0085.34301
[2] Diaconis, P.; Graham, R. L., Spearman’s footrule as a measure of disarray, J. Roy. Soc. Statist. Ser. B, 39, 262-268 (1977) · Zbl 0375.62045
[3] Flajolet, P.; Golin, M., Mellin transforms and asymptotics: the mergesort recurrence, Acta Inform., 31, 673-696 (1994) · Zbl 0818.68064
[4] M.A. Fligner, J.S. Verducci (Eds.), Probability models and statistical analysis, for ranking data, Lecture Notes in Statistics, vol. 80, Springer, Berlin, 1993.; M.A. Fligner, J.S. Verducci (Eds.), Probability models and statistical analysis, for ranking data, Lecture Notes in Statistics, vol. 80, Springer, Berlin, 1993.
[5] Greene, D. H.; Knuth, D. E., Mathematics for the Analysis of Algorithms (1981), Birkhäuser: Birkhäuser Boston · Zbl 0481.68042
[6] H.-K. Hwang, Asymptotic expansions of mergesort recurrences, Acta Inform., to appear.; H.-K. Hwang, Asymptotic expansions of mergesort recurrences, Acta Inform., to appear. · Zbl 0910.68058
[7] D.E. Knuth, The Art of Computer Programming, vol. III, Sorting and Searching. Addison-Wesley, Reading, MA. 1973.; D.E. Knuth, The Art of Computer Programming, vol. III, Sorting and Searching. Addison-Wesley, Reading, MA. 1973. · Zbl 0302.68010
[8] McGeoch, C. C.; Tygar, J. D., Optimal sampling strategies for quicksort, Random Struct. Algorithms, 7, 287-300 (1995) · Zbl 0835.68028
[9] Mannila, H., Measures of presortedness and optimal sorting algorithms, IEEE Trans. Comput., 34, 318-325 (1985) · Zbl 0556.68031
[10] K. Mehlhorn, Sorting presorted files, in: Theoretical Computer Science (4th GI Conference, Aachen, 1979), pp. 199-212, Lecture Notes in Computer Science, vol. 67, Springer Berlin, 1979.; K. Mehlhorn, Sorting presorted files, in: Theoretical Computer Science (4th GI Conference, Aachen, 1979), pp. 199-212, Lecture Notes in Computer Science, vol. 67, Springer Berlin, 1979. · Zbl 0395.68054
[11] Petersson, O.; Moffat, A., A framework for adaptive sorting, Discrete Appl. Math., 59, 153-179 (1995) · Zbl 0827.68032
[12] Sedgewick, R., Algorithms (1988), Addison-Wesley: Addison-Wesley Reading, MA
[13] Vitter, J. S.; Flajolet, P., Average-case analysis of algorithms and data structures, (Handbook of Theoretical Computer Science, vol. A, Algorithms and Complexity (1990), Elsevier: Elsevier Amsterdam), 431-524 · Zbl 0900.68251
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.