Enhanced Shell Sorting Algorithm

Authors: Basit Shahzad, Muhammad Tanvir Afzal

Abstract:

Many algorithms are available for sorting the unordered elements. Most important of them are Bubble sort, Heap sort, Insertion sort and Shell sort. These algorithms have their own pros and cons. Shell Sort which is an enhanced version of insertion sort, reduces the number of swaps of the elements being sorted to minimize the complexity and time as compared to insertion sort. Shell sort improves the efficiency of insertion sort by quickly shifting values to their destination. Average sort time is O(n1.25), while worst-case time is O(n1.5). It performs certain iterations. In each iteration it swaps some elements of the array in such a way that in last iteration when the value of h is one, the number of swaps will be reduced. Donald L. Shell invented a formula to calculate the value of ?h?. this work focuses to identify some improvement in the conventional Shell sort algorithm. ''Enhanced Shell Sort algorithm'' is an improvement in the algorithm to calculate the value of 'h'. It has been observed that by applying this algorithm, number of swaps can be reduced up to 60 percent as compared to the existing algorithm. In some other cases this enhancement was found faster than the existing algorithms available.

Keywords: Algorithm, Computation, Shell, Sorting.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332304

References:

[1] http://www.nist.gov/dada/html/shellsort.htm
[2] http://linux.wku.edu/~lamonml/algor/sort/shell.html
[3] http://oopweb.com/Algorithms/Documents/Sman/VolumeFrames.html?/ Algorithms/Documents/Sman/Volume/ShellSort_files/s_shl.htm
[4] Yedidyah Langsam, Moshe J. Augenstan, Aadrew M. Tenenbaum, "Data Structures using C and C++" , 2nd ed, Pearson Education, pp360-366
[5] Larry Nyhoff, "An introduction to Data Structures",2nd ed, pp: 581-585
[6] linux.wku.edu/~lamonml/algor/sort/sort.html
[7] www.cs.hope.edu/alganim/ccaa/shellsort.html
[8] www.inf.fhflensburg.de/lang/algorithmen/sortieren/shell/shellen.htm
[9] www.math.grin.edu/~stone/events/scheme-workshop/shellsort.html
[10] www.cs.odu.edu/~zeil/cs361/Lectures-f02/06sorting/shell/shell.html
[11] Robert Sedgewick, "Analysis of Shellsort and Related Algorithms", Proceedings of the Fourth Annual European Symposium on Algorithms},1996, pp: 1-11
[12] Marcin Ciura "Best Increments for the Average Case of Shellsort",Proceedings of the 13th International Symposium on Fundamentals of Computation Theory,2001, pp: 106ÔÇö117
[13] Jiang, T., Li, M., Vit'anyi, P.: The average-case complexity of Shellsort. Lecture Notes in Computer Science 1644 (1999), 453-462.
[14] Janson, S., Knuth, D. E.: Shellsort with three increments. Random Structures and Algorithms 10 (1997), 125-142.