What is Shell Sort?

In sorting, we have some basic types of algorithms that can sort the elements in a specific order. Often we use an array and sort its elements in numeric and lexicographical order.

Shell sort is an extension and improved version of insertion sort. In insertion sort, we take an element and compare it with the previous elements to check whether it is smaller or larger. Then, we swap the numbers accordingly where swapping takes place between two adjacent elements.

As shell sort is a variation of insertion sort, here, we do things a little differently until we can finally apply the insertion sort.

A shell sort is a sorting algorithm and an extension variant of insertion sort with improved average time complexity. In this sorting algorithm, we compare the far-right values with the far-left values and try to shift the smaller values on the left side and larger values on the right side.

As this algorithm is an extension of insertion sort, it uses insertion sorting as well. Here we compare the left values with the right values based on gaps or intervals. When we use the gap to compare the far elements, with each set of comparisons, we decrease the value of the gap. Once the algorithm reaches the point where the gap value is 1, it uses insertion sort.

Time Complexity of Shell Sort

Worst Time Complexity	O(n ² )
Average Time Complexity	O(n ^5/4 )
Best Time Complexity	O(n ^3/2 )

Important points :

This is a non-stable sorting algorithm since the elements with the same values can change their order of sequence.
It is an in-line sorting algorithm and as such, does not require extra arrays and temporary variables to store values.

An Example of Shell Sort: Let us have an ARRAY = [34, 32, 41, 9, 13, 18, 26, 43].

For the first set of comparison, the gap would be size (ARRAY)/2 i.e. 8/2 = 4 intervals.
Subsets comparison = {34,13}, {32,18}, {41,26}, {9,43}.
After swapping subsets the small value on the left side and the large value on the right side.
Subsets after swapping = {13,34}, {18,32}, {26,41}, {9,43}.
ARRAY will be after swapping = [13, 18, 26, 9, 34, 32, 41, 43].
For the second set of comparison we would create subset for 2 intervals and it will give 2 sub-lists {13, 26, 34, 41}, {18, 9, 32, 43}.
Once there is an interval of 1 with gap 1, we will apply the insertion sort on the array.

Advantages:

With improved Average time complexity, it is a very efficient algorithm for medium size arrays.
It is better than Insertion sort and 5 times faster than Bubble sort.

Disadvantages:

It is a complex algorithm.
Not as efficient as merge sort and quicksort.
Limited to use for small size arrays as the performance decreases with an increase in array size.

Implementation in Python

def shellSort(alist):
    sublistcount = len(alist)//2
    while sublistcount > 0:

      for startposition in range(sublistcount):
        gapInsertionSort(alist,startposition,sublistcount)

      print("After increments of size",sublistcount,
                                   "The list is",alist)

      sublistcount = sublistcount // 2

def gapInsertionSort(alist,start,gap):
    for i in range(start+gap,len(alist),gap):

        currentvalue = alist[i]
        position = i

        while position>=gap and alist[position-gap]>currentvalue:
            alist[position]=alist[position-gap]
            position = position-gap

        alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
shellSort(alist)
print(alist)

Output

After increments of size 4 The list is [20, 26, 44, 17, 54, 31, 93, 55, 77]
After increments of size 2 The list is [20, 17, 44, 26, 54, 31, 77, 55, 93]
After increments of size 1 The list is [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]

Implementation in C++

#include<iostream.h>
#include <conio.h>

void shell_sort(int arr[],int n)
{ 
   int temp;
   for(int gap=n/2;gap>0;gap/=2)
   {
     for(int i=gap;i<n;i++)
        {
         temp=arr[i];
         for(int j=i; j>=gap && arr[j-gap]>temp; j-=gap)
          {
              arr[j]=arr[j-gap];
          }
         arr[j]=temp;
        }
      }
    }

void main()
{
    clrscr();
    int len, arr[100];

    cout<<"How many elements do you want to enter into the array? :";
    cin>>len;

    for(int i=0;i<len;i++)
    {
        cin>>arr[i];
    }

    shell_sort(arr,len);

    cout<<"Sorted Array :";
    for(int j=0;j<len;j++)
    {
        cout<<arr[j]<<" ";
    }
    getch();
}

Output How many elements do you want to enter into the array? :6 11 9 12 14 6 37 Sorted Array: 6 9 11 12 14 37

Conclusion

That completes this article about shell sort. Hopefully, now you know how does the sorting algorithm work and how it can be implemented in C++ and Python. You can build a better understanding of this variation of the insertion sort by trying to code it in different ways, and in different programming languages.

All the best!

People are also reading:

What is Shell Sort?

Table of Content