Shell Sort Algorithm Visualizer using Matplotlib in Python
- Input Elements
- Generate Elements
Shell Sort, commonly known as Shell's approach, is an extension of Insertion Sort that introduces decreasing increments to increase efficiency by allowing exchanges of far-apart elements. According to M Saqib in 2021, the sorting algorithm known as Shell Sort was named in honor of its creator, Donald Lewis Shell. Shell first introduced this algorithm in a research paper titled "A High-Speed Sorting Procedure," which was published in the Communications of the ACM journal in July 1959. Shell sort is a sorting method that is inspired by the insertion sort technique. Unlike insertion sort, which requires substantial element shifting when a smaller value is on the far right and has to be relocated to the far left, Shell sort requires little element moving. Shell sort successfully minimizes its time complexity by utilizing the information that performing insertion sort to a partly sorted array takes fewer motions.
This method begins by sorting pairs of items that are far off from one another, gradually reducing the distance between the elements to be compared. This will move the out-of-place elements much faster than a simple-nearest exchange. This algorithm also uses insertion sort on widely spread elements and then sorts the less widely spaced elements called intervals or gaps. The interval or gap will gradually be reduced based on the specific sequence. The array can be considered h-sorted if all sublist of every hth element are sorted. This algorithm is composed of the following steps:
- Based on the list size, choose a starting increment interval.
- Repeat the operation within a loop with a reduced interval size set by a specific sequence.
- To complete the array sorting, use insertion sort with an interval size of 1 within the loop.
- The array is deemed fully sorted when the loop is finished.
The array members gradually approach their suitable locations with each iteration of the algorithm's outer loop. These are some of the optimal sequences that are commonly used to get the increment interval in shell sort algorithms:
- Shell's original sequence: Starting with a gap equal to half the total number of components (N), this sequence reduces the gap by halves until it reaches
- Formula: 𝑵/𝟐^𝒉 ; where h initial value is 1
- Sequence: N/2, N/4, …, 1
- Knuth's increments: It uses a formula to increment the interval or gap.
- Formula: h = h * 3 + 1; where h is the interval that has an initial value of 1
- Sequence: 1, 4, 13, 40, …
- Sedgewick's increment: This uses alternatively two combined arithmetic progressions to generate the incremental interval.
- Formula: 𝟒^(𝒉+𝟏) + 𝟑 ∗ 𝟐^𝒉 + 𝟏 ; where h initial value is 0
- Sequence: 1, 8, 23, 77, 281, …
- Hibbard’s increment: It uses a formula to generate the incremental value of the interval or gap.
- Formula: 𝟐^(𝒉 − 𝟏); where k initial value is 0
- Sequence: 0, 1, 3, 7, 15, …
- Papernov & Stasevich increment: It specifies the set of gap values used in the Shell sort algorithm. It follows a simple formula that generates increments based on the expression:
- Formula: 2h+1, where h starts from 0.
- Sequence: 1, 3, 5, 9, 17, …
- Pratt: It is a sequence generated by considering all numbers that are the
product of power of 2, 3, and 5, arranged in ascending order. These
numbers are called “harmonic numbers”.
- Formula: 𝟐^𝒉 ∗ 𝟑^𝒊; where h and i is greater than or equal to 0
- Sequence: 1, 2, 3, 4, 6, 8, …
The efficiency of the sorting process may be greatly improved by selecting a suitable sequence. Different sequences could work better with various input sizes and distributions, and their effectiveness may change based on the details of the data being sorted.
ShellSort (A[], sizeof(A[]))
# Sorts a given array by Shell Sort using Shell’s original sequence
# Input: An array A[] of n orderable elements
# Output: Array A[] sorted in ascending order
interval = sizeof(A[]) / 2
while interval > 0 do
for i ← interval to n – 1 do
temp ← A[i]
h ← i
while h >= interval and A[h – interval] > temp do
A[h] ← A[h - interval]
h ← h – interval
A[h] ← temp
interval ← interval / 2
- Worst-case time complexity: Shell sort has a worst-case time complexity of less than or equal to O(𝒏^𝟐), where n is the number of elements in the array. However, the actual worst-case temporal complexity can vary depending on the interval sequence. According to the Poonen Theorem developed by mathematician Bjorn Poonen, some worst-case complexity lie within the range of Θ(𝑁^2/(𝑙𝑜𝑔 𝑁)^2), Θ(𝑁^2/𝑙𝑜𝑔 𝑙𝑜𝑔 𝑁), Θ(𝑁(𝑙𝑜𝑔 𝑁)^2), or somewhere in between. These worst-case complications represent the most significant number of comparisons and swaps necessary for array sorting.
- Best-case time complexity: Shell sort has an O(𝐧 ∗ 𝐥𝐨𝐠 𝒏) best-case time complexity. This happens when the array is sorted or almost sorted, and the intervals used for efficient sorting group items are already in their right placements.
- Average-case time complexity: Shell sort is commonly expected to have an average-case time complexity of about O(𝒏^𝟏.𝟐𝟓), which indicates a sub quadratic growth rate. The average complexity takes into account various input distributions and assumes that the components are distributed randomly. The value 1.25 implies that Shell Sort outperforms quadratic algorithms but not linearithmic ones such as Merge Sort or Quick Sort.
- Afzal, Tanveer & Shahzad, Basit & Aslam, Salman. (2007). ENHANCED SHELL SORT ALGORITHM.
- Data Structure and Algorithms - Shell Sort - Tutorialspoint. (n.d.). Www.tutorialspoint.com. https://www.tutorialspoint.com/data_structures_algorithms/shell_sort_algorithm.htm
- GeekforGeeks. (2014, June 16). ShellSort. GeeksforGeeks. https://www.geeksforgeeks.org/shellsort/
- Khandelwal, N. (2020). Shell Sort: Advantages and Disadvantages. Shiksha.com. https://www.shiksha.com/online-courses/articles/shell-sort-advantages-and�disadvantages/
- Levitin, A. (2012). The Design and Analysis of Algorithms Introduction to.
- M. Saqib. (2021, February 28). Shell Sort Algorithm Implementation in C: Knuth’s and Hibbard’s Intervals - A High-Speed Sorting Procedure. Www.mycplus.com. https://www.mycplus.com/featured-articles/shell-sort-algorithm/
- Poonen, B. (1993). The Worst Case in Shellsort and Related Algorithms. Journal of Algorithms, 15(1), 101–124. https://doi.org/10.1006/jagm.1993.1032
- Sedgewick, R. (1996). Analysis of Shellsort and related algorithms. 1–11. https://doi.org/10.1007/3-540-61680-2_42
- Sedgewick, R. (1988). Algorithms. Pearson Education India.
- Shell Sort (With Code). (n.d.). Www.programiz.com. https://www.programiz.com/dsa/shell-sort
- Shell Sort in Data Structure. (n.d.). Https://Techvidvan.com. https://techvidvan.com/tutorials/shell-sort/
- Shellsort. (2023, May 19). Wikipedia. https://en.wikipedia.org/wiki/Shellsort#Gap_sequences
- Simplilearn. (2023, February 20). Shell Sort Algorithm In Data Structures: Overview, Time Complexity & More | Simplilearn. Simplilearn.com. https://www.simplilearn.com/tutorials/data-structure-tutorial/shell-sort
- Yu, H.-L. (1984). INVESTIGATIONS OF zs:r_,? SHELL SORT. https://shareok.org/bitstream/handle/11244/16144/Thesis-1984-Y94i.pdf?sequence=1