Shell Sort in Data Structure

Shell sort is one of the highly efficient algorithms. It is based on the insertion sort technique. The major difference between insertion sort and shell sort is that shell sort avoids large shifts of the elements. Shell sort first sorts the elements that are far and continuously keeps on decreasing the interval between the far elements.

The space between the far elements is called interval. Interval for the shell sort is calculated by various methods.

Interval calculation in Shell Sort

Interval in shell sort can be reduced by using the optimal sequence. Some optimal sequences that can be used in shell sort are:

• Shell’s original sequence: N/2, N/4, …. 1
• Knuth’s Sequence: 1, 4, 13, ….., (3n – 1) / 2
• Sedgwick’s sequence: 1,8,23,77,281,1073,4193,16577… 4j+1+3.2j+1
• Hibbard’s sequence: 1,3,7,15,31,63,127,255,511….
• Papernov & Stasevich sequence: 1,3,5,9,17,33,65,….
• Pratt: 1,2,3,4,6,9,8,12,18,27,16,24,36,54,81,…

Shell Sort Procedure

1. Sort the columns by using insertion sort after arranging the elements in the tabular form
2. Repeat Step 1 with a smaller number of longer columns each time. Do this in such a way that at the end, only one column of data is left to be sorted.

Shell Sort Algorithm Steps

1: set flag = 1, interval = n
2: while flag = 1 or interval > 1
3: set flag = 0
4: set interval = (interval + 1) / 2
5: for i = 0 to i < (n – interval)
6: if array[i + interval] > array[i]
swap array[i + interval], array[i]
set flag = 0
[End of for]
[End of while]
7: Stop

Pseudocode for Shell Sort

procedure Shellsort(array)

   while interval < array.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 

      for out = interval; out < array.length; out ++ 
      
      insertValue = array[out]
      inner = out;

         while inner > interval -1 && array[inner - interval] >=   insertValue 
            array[inner] = array[inner - interval]
            inner = inner - interval
         end while

         array[inner] = insertValue

      end for

      interval = (interval -1) /3;	  

   end while
   
end procedure

Working of shell sort

Let’s sort the characters in the word “DATAFLAIR” by the bubble sort technique.

We will be using knuth’s sequence for interval:

Interval = integer (N/2) = integer (9/2) = 4

Iteration 1: Divide the array into subarray containing no. of elements = interval

Iteration 2: swap the elements with their corresponding elements as shown above

Iteration 3: update interval value to 1

Iteration 4: swap the elements with their corresponding elements as shown above

Iteration 5: sort the remaining array using insertion sort

Final sorted array:

We can clearly see that the order of elements with the same value ‘A’ is changed in the final sorted array in the above example. Therefore, shell sort is not a stable algorithm.

Shell Sort Implementation in C

#include <stdio.h>

void ShellSort(int array[], int len) 
{
  for (int interval = len / 2; interval > 0; interval = interval/2) 
  {
    for (int i = interval; i < len; i =i+ 1) 
    {
      int temp = array[i];
      int j;
      for (j = i; j >= interval && array[j - interval] > temp; j -= interval) 
      {
        array[j] = array[j - interval];
      }
      array[j] = temp;
    }
  }
}

int main() 
{
  int array[] = {21, 3, 49, 82, 91, 36, 61, 77,53};
  int len = sizeof(array) / sizeof(array[0]);
  ShellSort(array, len);
  printf("Sorted array: \n");
   for (int i = 0; i < len; ++i) 
   {
    printf("%d  ", array[i]);
  }
}

Implementation of Shell Sort in C++

#include<iostream>
using namespace std;

void ShellSort(int array[], int len) 
{
  for (int interval = len / 2; interval > 0; interval = interval/2) 
  {
    for (int i = interval; i < len; i =i+ 1) 
    {
      int temp = array[i];
      int j;
      for (j = i; j >= interval && array[j - interval] > temp; j -= interval) 
      {
        array[j] = array[j - interval];
      }
      array[j] = temp;
    }
  }
}

int main() 
{
  int array[] = {21, 3, 49, 82, 91, 36, 61, 77,53};
  int len = sizeof(array) / sizeof(array[0]);
  ShellSort(array, len);
  cout << "Sorted array:" ;
   for (int i = 0; i < len; ++i) 
   {
    cout << " " << array[i];
  }
}

Shell Sort Implementation in JAVA

import java.util.Arrays;

public class ShellSort 
{
  void shellSort(int array[], int len) 
  {
  for (int interval = len / 2; interval > 0; interval = interval / 2) 
  {
    for (int i = interval; i < len; i = i+ 1) 
    {
    int temp = array[i];
    int j;
    for (j = i; j >= interval && array[j - interval] > temp; j = j- interval) 
    {
      array[j] = array[j - interval];
    }
    array[j] = temp;
    }
  }
  System.out.println("Sorted Array: ");
  for (int i=0;i<len;i++)
  System.out.print(array[i]+" ");
  }
  
  public static void main(String args[]) 
  {
  int[] array = { 21, 3, 49, 82, 91, 36, 61, 77,53 };
  int len = array.length;
  ShellSort ss = new ShellSort();
  ss.shellSort(array, len);
  }
}

Implementation of Shell Sort in Python

def shellSort(array, n):
    
    interval = n // 2
    while interval > 0:
        for i in range(interval, n):
            temp = array[i]
            k = i
            while k >= interval and array[k - interval] > temp:
                array[k] = array[k - interval]
                k = k -  interval

            array[k] = temp
        interval =interval // 2


array = [21, 3, 49, 82, 91, 36, 61, 77,53]
size = len(array)
shellSort(array, size)
print('Sorted Array:')
print(array)

Complexity of Shell Sort

Applications of shell sort

Shell sort is used:

• To call a stack user head
• When recursion exceeds the limit
• Shell sort reduces the space between elements having close value. More beneficial than insertion sort.

Conclusion

Shell sort is one the most efficient sorting algorithm for large datasets. This technique is based on insertion sort but it reduces the no. of swaps considerably. Shell sort does not require extra memory which makes it an overall efficient algorithm for sorting. In the working of shell sort, we proved that shell sort is not a stable sorting algorithm.