ANALYSIS OF SHELLSORT ALGOITHMS
Main Article Content
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.
Â
Downloads
Article Details
COPYRIGHT
Submission of a manuscript implies: that the work described has not been published before, that it is not under consideration for publication elsewhere; that if and when the manuscript is accepted for publication, the authors agree to automatic transfer of the copyright to the publisher.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work
- The journal allows the author(s) to retain publishing rights without restrictions.
- The journal allows the author(s) to hold the copyright without restrictions.
References
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.