Shell Sort in Data Structure

Shell sort is a special case of insertion sort. It was designed to overcome the drawbacks of insertion sort. Thus, it is more efficient than insertion sort. In shell sort, we can swap or exchange the far away items in addition to adjacent items.

What is Shell Sort?

In insertion sort, we could move the elements ahead only by one position at a time. If we wish to move an element to a faraway position in insertion sort, a lot of movements were involved thus increasing the execution time. Shell sort overcomes this problem of insertion sort by allowing movement and swap of far-away elements as well.

This sorting technique works by sorting elements in pairs, far away from each other and subsequently reduces their gap. The gap is known as the interval. We can calculate this gap/interval with the help of Knuth’s formula.

Knuth’s formula

Let h be the interval having an initial value = 1
Then, h = h*3 + 1

Follow TechVidvan on Google & Stay updated with latest technology trends

Characteristics of Shell Sort

  • Comparison-based sorting technique.
  • Inplace sorting technique just like insertion sort.
  • Works very well for medium-sized datasets.
  • Unstable sorting technique.

Working of Shell Sort

Suppose we wish to sort the following list of elements: 71, 7, 28, 22, 36, 12, 15, 22, 4.
The first step in shell sort is to decide the gap/interval. Let us take interval = 4. Thus, we will select pairs of elements present at an interval 4 from each other and swap them if they are out of order.

Shell Sort working

On swapping these pairs, the array will be:

Shell Sort Example

After performing this step, we will simply apply insertion sort on this array.

Iteration 1:

Shell Sort Iterations

Iteration 2:

Shell Sort Iterations

Iteration 3:

Shell Sort Working

Iteration 4:

Shell Sort Iterations

Iteration 5:

Shell Sort Iterations

Iteration 6:

Shell Sort Working

Iteration 7:

Shell Sort Iteration

 

Thus, the final sorted array is:

Shell Sort Output

Shell sort reduces the number of inversions by swapping far away elements in the first step. Hence, it is simply a variation of insertion sort.

Algorithm for Shell Sort

Step 1: Initialize the gap size i.e. h
Step 2: Divide the array into sub-arrays each having interval of h
Step 3: Sort the sub-arrays with insertion sort
Step 4: Reduce the value of h
Step 5: Repeat the above steps until the array is sorted

Pseudo-code of Shell Sort

procedure Shell_sort(Array, n)  //n = size of array
    while gap < length(Array) /3 :
        gap = interval * 3 + 1	    
    END while loop
   
    while gap > 0 :
        for (outer = gap; outer < length(Array); outer++):
            Insertion_value = Array[outer]
            inner = outer;
            while inner > gap-1 && Array[inner - gap] >= Insertion_value:
                Array[inner] = Array[inner - gap]
                inner = inner - gap
            END while loop
            Array[inner] = Insertion_value
        END for loop

        gap = (gap -1) /3;	  

    end while loop
END Shell_sort

Shell Sort Implementation in C

#include <stdio.h>
void Shell_sort(int Array[], int N)
{
    int gap, j, i, Temp;
    for (gap = N/2; gap > 0; gap = gap/2){
        for (i = gap; i < N; i++) {
            Temp = Array[i];
            for (j = i; j >= gap && Array[j - gap] > Temp; j = j-gap){
            Array[j] = Array[j - gap];
        }
        Array[j] = Temp;
        }
    }
}
void Display_array(int arr[], int n){
  for(int i=0; i<n; i++){
     printf("%d  ", arr[i]);
  }
  printf("\n");
}

int main(){
    int array[]={21, 12, 14, 46, 7, 25, 10, 62, 19, 31, 1};
    int size =sizeof(array) / sizeof(int);
    Shell_sort(array, size);
    printf("Sorted array is: \n");
    Display_array(array, size);
    return 0;
}

Shell Sort Implementation in C++

#include <bits/stdc++.h>
void Shell_sort(int Array[], int N)
{
    int gap, j, i, Temp;
    for (gap = N/2; gap > 0; gap = gap/2){
        for (i = gap; i < N; i++) {
            Temp = Array[i];
            for (j = i; j >= gap && Array[j - gap] > Temp; j = j-gap){
            Array[j] = Array[j - gap];
        }
        Array[j] = Temp;
        }
    }
}
void Display_array(int arr[], int n){
    for(int i=0; i<n; i++)
        cout<< arr[i];
    cout << endl;
}

int main(){
    int array[]={21, 12, 14, 46, 7, 25, 10, 62, 19, 31, 1};
    int size =sizeof(array) / sizeof(int);
    Shell_sort(array, size);
    cout<< "Sorted array is: \n";
    Display_array(array, size);
    return 0;
}

Implementation of Shell Sort in Java

class ShellSort
{

  static void Display_array(int arr[])
  {
    int N = arr.length;
    for (int i=0; i<N; ++i)
      System.out.print(arr[i] + " ");
    System.out.println();
  }

  int shell_sort(int Array[])
  {
    int N = Array.length;
    for (int gap = N/2; gap > 0; gap = gap/2)
    {
      for (int i = gap; i < N; i += 1)
      {
        int Temp = Array[i];
        int j;
        for (j = i; j >= gap && arr[j - gap] > Temp; j =j- gap)
          Array[j] = Array[j - gap];
        Array[j] = Temp;
      }
    }
    return 0;
  }

  public static void main(String args[])
  {
    int arr[] = {21, 12, 14, 46, 7, 25, 10, 62, 19, 31, 1};
    System.out.println("Before sorting, the array is: ");
    Display_array(arr);

    ShellSort ob = new ShellSort();
    ob.shell_sort(arr);
    System.out.println("Array after sorting: ");
    Display_array(arr);
  }
}

Shell Sort Implementation in Python

def Shell_sort(Array):
  gap = len(Array) // 2 
  while gap > 0:
    i = 0
    j = gap
    while j < len(Array):
      if Array[i] >Array[j]:
        Array[i],Array[j] = Array[j],Array[i]
      i++
      j++
    while i - gap != -1:
      if Array[i - gap] > Array[i]:
        Array[i-gap],Array[i] = Array[i],Array[i-gap]
      i = i-1
    gap = gap//2

list = 21, 12, 14, 46, 7, 25, 10, 62, 19, 31, 1]
print("Input array:",list)
Shell_sort(list)
print("Sorted array is: ",list)

Complexity of Shell Sort

Scenario Time complexity
Worst caseO(n2)
Average caseθ(n log(n)2)
Best caseΩ(n log(n))

The space complexity of shell sort is O(1).

Applications of Shell Sort

1. Shell sort is a replacement of insertion sort when insertion sort is taking too much execution time.
2. We use shell sort when the call of the stack is overhead.
3. Shell sort is applicable when recursion exceeds a particular limit.

Conclusion

Shell sort is another sorting technique that is highly efficient for medium to large-sized datasets. It is comparison-based and unstable. It helps to reduce the number of operations of insertion sort.

In this article, we have studied what is shell sort, its working and its implementation in various programming languages. We have also seen some real-life applications of shell sort.

You give me 15 seconds I promise you best tutorials
Please share your happy experience on Google | Facebook


Leave a Reply

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