Email this article ANALYSIS OF SHELLSORT ALGOITHMS
Abstract
Shellsort is a comparison sort that uses insertion sort at each iteration to make a list of interleaved elements nearly sorted so that at the last iteration the list is almost sorted. The time complexity of Shellsort is dependent upon the method of interleaving (called increment sequence) giving variants of Shellsort. However, the problem of finding proper interleaving to achieve the minimum time complexity of O(n log n) is still open. In this paper, we have analyzed the performance of variants of Shellsort based on their time complexity. Our measure of time complexity is independent of the machine configuration and considers all the operations of a sorting process. We found that the interleaving method or increment sequence proposed by Sedgewick performs best among the analyzed variants.
Keywords
Full Text:
PDFReferences
D.L.Shell, “A High Speed Sorting Procedure”, Communications of the ACM, volume 2, issue 7, pp 30-32, July 1959. DOI: 10.1145/368370.368387.
Michael T. Goodrich, “Randomized Shellsort: A Simple Data-Oblivious Sorting Algorithm”, Journal of the ACM, volume 58, issue 6, 2001.
R.M.Frank, R.B. Lazarus, “A High Speed Sorting Procedure”, Communications of the ACM, volume 3, issue 1, pp 20-22, January 1960.
A.A.Papernov and G.Stasevich, “A Method of Information Sorting in Computer Memories”, Problems in Information Transmission, volume 1, issue 3, pp 63-75, 1965.
V.R.Pratt, “Shellsort and Sorting Networks”, No. Stan-CS-72-260, Standford University CA Department of Computer Science, February 1972. Available from: https://apps.dtic.mil/dtic/tr/fulltext/u2/740110.pdf
Janet Incerpi and Robert Sedgewick, “ Improved Upper Bounds on Shellsort”, Journal of Computer and System Sciences, volume 31, issue 2, pp 210-224, October 1985.
Andrew Chi-Chih Yao, “An Analysis of (h, k, 1) – Shellsort”, Journal of Algorithms, volume 1, issue 1, pp 14-50, March 1980.
Donald. E. Knuth, “Art of Computer Programming: volume 3 Sorting and Searching”, Second Edition, Addison-Wesley, 1998.
Robert Sedgewick, “A New Upper Bound for Shellsort”, Journal of Algorithms, volume 7, issue 2, pp 159-173, June 1986.
Svante Janson and Donald E. Knuth, “Shellsort with Three Increments”, Random Structures and Algorithms, volume 10, issue 1, pp 125-142, January 1997.
Thomas N. Hibbard, “An Empirical Study of Minimal Storage Sorting”, Communications of the ACM, volume 6, issue 5, pp 206-213, 1963.
Paul Vitnayi, “On the Average-case Complexity of Shellsort”, Random Structures and Algorithms, volume 52, issue 2, pp 354-363, 2018.
M.A. Weiss, “Shellsort with Constant Number of Increments”, Algorithmica, volume 16, issue 6, pp 649-654, December 1996.
Richard Simpson, Shashidhar Yachavaram, “Faster Shellsort Sequences: A Genetic Algorithm Application”, Computers and Their Applications, 1999.
Naoyuki. Tokuda, “An Improved Shellsort”, IFIP 12th World Computer Congress on Algorithms, Software, Architecture – Information Processing, 1992.
Bronislava Brejova, “Analyzing Variants of Shellsort”, Information Processing Letters, volume 79, issue 5, pp 223-227, September 2001.
Tao Jing, Ming Li, Paul Vitanyi, “Average-case Complexity of Shellsort”, International Colloquium on Automata, Languages and Programming, 1999.
Janet Incerpi and Robert Sedgewick, “Practical Variations of Shellsort”, Doctoral Dissertation, INRIA, 1986.
J.L.Ramirez-Alfonsin, “Complexity of the Frobenius Problem”, Combinatorica, volume 16, issue 1, pp 143-147, March 1996.
Thomas H. Cormen, Charles E Leiserson, Ronald R. Rivest, Clifford Stein, “Introduction to Algorithms”, 3rd Edition, MIT Press and Prentice Hall of India, February 2010.
D. Ghoshdastidar and Mohit Kumar Roy, “A Study on the Evaluation of Shell’s sorting Technique”, The Computer Journal, volume 18, issue 3, pp 234-235, 1975.
DOI: https://doi.org/10.26483/ijarcs.v10i3.6433
Refbacks
- There are currently no refbacks.
Copyright (c) 2019 International Journal of Advanced Research in Computer Science
