What is Shell Sort

By | September 11, 2019

In sorting algorithms, we have some basic type of algorithms which 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 took an element and compare it with its previous elements to check whether it is smaller or larger and swap the numbers where swapping take place between two adjacent elements, as shell sort is a variation of insertion sort here, we swap the element, of the far end.

What is Shell sort?

A shell sort is a sorting algorithm and an extension variant of insertion sort with improved Average time complexity. In Shell sort, we compare the far-right values with 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 so it uses insertion sorting as well.  Here we compare the left values with the right values based on gaps or interval. When we use the gap to compare the far elements, with each set of comparison we decrease the value of gap, once the algorithm is done with gap value 1, it uses insertion sort at last.

Shell Sort Time Complexity

Worst Time Complexity O(n2)
Average Time Complexity O(n5/4)
Best Time Complexity O(n3/2)
  • Shell sort is a Non-Stable sorting algorithm, here elements with the same values can change their order of sequence
  • It is an In-Line sorting algorithm and does not require extra arrays and temporary variables to store values.

Shell Sort Example:

  • ARRAY = [34, 32, 41, 9, 13, 18, 26, 43]

For 1st set of comparison the gap would be size (ARRAY)/2 = 8/2 = 4 intervals

Subsets comparison = {34,13}, {32,18}, {41,26}, {9,43}

After swapping subsets the small value on left side and large value on 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 2nd set of comparison we would create subset for 1 interval and it will give 2 sub-lists {13, 26, 34, 41}, {18, 9, 32, 41}.

Once there is an interval of 1 with gap 1 we will apply the insertion sort on the array.

Shell Sort Advantages and Disadvantages:

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 that much efficient as Merge and quicksort.
  • It is limited with small size arrays.
  • With large-size array its performance becomes slow.

Shell Sort Implementation:

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]

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 in 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 in the array? :6
11
9
12
14
6
37
Sorted Array: 6 9 11 12 14 37

Leave a Reply

Your email address will not be published. Required fields are marked *