Shell Sort

Shell Sort

Shell Sort is a variation of Insertion Sort. In this sort, we move the elements only one position forward.

Shellsort is the generalization of insertion sort, which overcomes the drawbacks of insertion sort by compared the elements separated by a gap of some positions.

 

 

This algorithm first sorts the elements are far away from each other, then it afterward reduces the gap between them. This gap is known as interval.

The interval is calculated by using the Knuth’s formula given below

    1. hh = h * 3 + 1
    2. where, ‘h’ is the interval having initial value 1.

Algorithm

ShellSort(a, n)
for (interval = n/2; interval > 0; interval /= 2)  
for ( int i = interval; i < n; i += 1)  
temp = a[i];  
for (j = i; j >= interval && a[j - interval] > temp; j -= interval)  
a[j] = a[j - interval];   
a[j] = temp;  
End ShellSort

 

Example of shellsort

 

Suppose the elements of array are

 

Shell Sort Algorithm

 

 

The original sequence of shellsort is N/2, N/4,….,1 as the intervals.

In the first loop, n is equal to 8 is size of the array, the elements are lying at the interval of 4 (n/2 = 4).If elements are not in oreder then elements will be compared and swapped.

In the first loop, the element at the zero position will be compared with the element at fourth position. If the zero element is greater then it will be swapped with element at 4th position. Otherwise, it remains the same position. This process will same and continue for the remaining elements.

At the interval of four, the sub lists are {33, 12}, {31, 17}, {40, 25}, {8, 42}.

 

Shell Sort Algorithm

 

 

 

Now, the elements compare the values in every sub-list. After comparing the element, we have to swap this element, if required in the original array. After comparing and swapping the elements, the updated array look as follows –

 

Shell Sort Algorithm

 

 

In the 2nd loop, elements are lying at the interval of 2 (n/4 = 2), and n = 8.

Now, we are taking the interval of 2 to sort the array. With an interval of 2, two sublists will be crreated they are – {12, 25, 33, 40}, and {17, 8, 31, 42}.

 

Shell Sort Algorithm

 

 

 

Now, Again compare the values in every sublist. After comparing the element, we have to swap this element if required in the original array. After comparing and swapping the, the updated array look as follows –

 

Shell Sort Algorithm

 

 

In the 3rd loop, elements are lying at the interval of 1 (n/8 = 1), where n = 8. Lastly, we use the interval of value 1 to sort the the array of elements. In this step, shell sort using the insertion sort to sort the array elements.

 

 

Shell Sort Algorithm

 

 

 

This is array is sorted in ascending order.

 

Program of shellsort in C

#include <stdio.h>

// Shell sort
void shellSort(int array[], int n) {
  // Rearrange elements 
  for (int interval = n / 2; interval > 0; interval /= 2) {
    for (int i = interval; i < n; 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;
    }
  }
}

// Print the array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

// Driver code
int main() {
  int data[] = {9, 8, 3, 7, 5, 6, 4, 1};
  int size = sizeof(data) / sizeof(data[0]);
  shellSort(data, size);
  printf("Sorted array: \n");
  printArray(data, size);
}

Output

Sorted array: 
1  3  4  5  6  7  8  9

 

 

Program of shell sort in C++

#include <iostream>
using namespace std;

// Shell sort
void shellSort(int array[], int n) {
  //arrange the elements 
  for (int interval = n / 2; interval > 0; interval /= 2) {
    for (int i = interval; i < n; 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;
    }
  }
}

// Print an array
void printArray(int array[], int size) {
  int i;
  for (i = 0; i < size; i++)
    cout << array[i] << " ";
  cout << endl;
}

// Driver code
int main() {
  int data[] = {9, 8, 3, 7, 5, 6, 4, 1};
  int size = sizeof(data) / sizeof(data[0]);
  shellSort(data, size);
  cout << "Sorted array: \n";
  printArray(data, size);
}

Output

Sorted array: 
1 3 4 5 6 7 8 9

 

Program of shellsort in Python

def shellSort(array, n):

    #arrange the elements 
    interval = n // 2
    while interval > 0:
        for i in range(interval, n):
            temp = array[i]
            j = i
            while j >= interval and array[j - interval] > temp:
                array[j] = array[j - interval]
                j -= interval

            array[j] = temp
        interval //= 2


data = [9, 8, 3, 7, 5, 6, 4, 1]
size = len(data)
shellSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)

Output

Sorted Array in Ascending Order:
[1, 3, 4, 5, 6, 7, 8, 9]

Program of shell sort in Java

import java.util.Arrays;

// Shell sort
class ShellSort {

  // Rearrange the elements 
  void shellSort(int array[], int n) {
  for (int interval = n / 2; interval > 0; interval /= 2) {
    for (int i = interval; i < n; 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;
    }
  }
  }

  // Driver code
  public static void main(String args[]) {
  int[] data = { 9, 8, 3, 7, 5, 6, 4, 1 };
  int size = data.length;
  ShellSort ss = new ShellSort();
  ss.shellSort(data, size);
  System.out.println("Sorted Array in Ascending Order: ");
  System.out.println(Arrays.toString(data));
  }
}

Output

Sorted Array in Ascending Order: [1, 3, 4, 5, 6, 7, 8, 9]

 

Shell sort complexity

The time complexity of Shellsort in the best case, average case, and worst case is as follows

 

 

1. Time Complexity

 

Case Time Complexity
Best Case O(n*logn)
Average Case O(n*log(n)2)
Worst Case O(n2)

 

2. Space Complexity

Space Complexity O(1)
Stable NO

 

Shell Sort Applications

 

  • Shellsort used to  calling a stack is overhead. uClibc library uses this sort.
  • Recursion exceeds a limit. bzip2 compressor uses it.
  • Insertion sort does not perform good when the close elements are far apart and Shell sort helps in reducing the distance between the close elements, therefore, there will be less no. of swappings to be performed.

 

Read more, Heap sort

Share this post

Leave a Reply

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