The shell sort, also known as the “diminishing increment sort,” improves on the insertion sort by dividing the original list into multiple smaller sub lists, each of which is sorted with an insertion sort. When the smaller value is on the far right and must be pushed to the far left, this technique avoids huge shifts as in insertion sort. This algorithm sorts widely spaced elements first, then sorts the less widely spaced elements using insertion sort. Interval is the name for this spacing. This interval is calculated using Knuth’s formula.
Knuth’s Formula
h = h * 3 + 1
Where h is an interval with a starting value 1
Working of Shell Sort
- In the shell sort if the array size is N = 8, the elements in the interval of N/2 = 4 are compared and swapped if they are out of order in the first loop. The 0th element and the 4th element are compared. If the value at 0th position is greater than the value at 4th, the 4th element is recorded first in the temp variable, followed by the 0th element (i.e. greater element) in the 4th position and the element recorded in temp is stored in the 0th position. This procedure is repeated for the remaining items.
- In the second loop, an interval of N/4 = 8/4 = 2 is chosen, and the elements that fall inside this range are sorted once more. At this point, you might be confused. The elements at position 4 and 2 are compared. The elements in the 2nd and 0th positions are compared as well. The array’s elements that fall within the current interval are compared.
- The technique is repeated for the remaining items.
- Finally, when N/8 = 8/8 = 1, the array elements in the interval of 1 are sorted. The array has now been sorted completely.
Consider the following example to have a better understanding of how shell sort works. Unsorted array is:
Make a virtual sub-list of all values in the interval of 4. So, in this case sub lists will be: (34, 13), (32, 18), (41, 26) and (9, 43).
We compare the values in each sub-list and swap them in the original array if necessary. This is how the new array should look after swapping smaller element with greater one in each sub list to make an ordered sub list:
Then we take a interval of 2 and divide it into two sub-lists. Each sublist will be (13, 26, 34, 41) and (18, 9, 32, 43) which are displayed below:
We compare the values in the original array and, if necessary, swap them. This is how the array should look after this step:
Finally, we use interval 1 to sort the rest of the array. The array is sorted by shell sort using insertion sort. The following is a step-by-step guide:
Shell Sort Algorithm
Step 1: Set the value of h.
Step 2: Separate the list into smaller sub-lists with the same h interval.
Step 3: Using insertion sort, sort these sub-lists.
- Read ARRAY
- Repeat step 3 to 8 for I=1 to N-1
- Set Temp=ARRAY[I]
- Set J=I-1
- Repeat step 6 and 7 while Temp<ARRAY[J] AND J>=0
- Set ARRAY[J+1]=ARRAY[J] [Moves element forward]
- Set J=J-1 [End of step 5 loop]
- Set ARRAY[J+1]=Temp [Insert element in proper place] [End of step 2 loop]
- Exit
Complexity of Shell Sort
Shell sort is an insecure sorting algorithm since it ignores the elements that fall in between the intervals. Following is the description on the time and space complexity of shell sort:
Time Complexity
Complexity in the worst-case scenario is less than or equal to O ({n}^{2}). Shell sort’s worst-case complexity is always less than or equal to O({n}^{2}). The worst case complexity for shell sort, according to the Poonen Theorem, is ({Nlog N})^{2}/({log log N})^{2}, or ({Nlog N})^{2}/log log N), or ({N(log N})^{2}), or something in between. O(n*log n) is the best case complexity. The total number of comparisons for each interval (or increment) is equal to the size of the array when it is already sorted. O(n*log n) is the average case complexity. It’s somewhere around O({n}^{1.25}). The degree of difficulty is determined by the interval picked. The above complexity vary depending on the increment sequences used. The best increment sequence has yet to be discovered.
Space Complexity
Shell sort has a space complexity of O(1).
Advantages of Shell Sort
- The shell sort technique is only efficient for arrays with a finite number of elements.
- The shell sort algorithm outperforms the bubble sort algorithm by 5.32 times.
Disadvantages of Shell Sort
- The shell sort algorithm has a more complicated structure and is a little more difficult to comprehend.
- The merge sort, rapid sort, and heap sort algorithms are all much slower than the shell sort method.