Shell sort in Data structure is one of the sorting technique. It is a rarely used technique as it seems difficult for implementing.

Shell Sort

What is Shell Sort?: The Shell sort in Data structure is also known as the shells method. It is the generalization of bubble sort or Insertion sort technique. It is mainly based on insertion sort. In insertion sort, we can move element one place ahead, when an element has to be moved a far ahead, it involves many movements. The main idea for a shell sort in Data Structure is to exchange a far element.

Shell sort technique

In this shell sort technique, we have an N number of a list which is unsorted in this technique, we consider the N number in a list and depending upon that we make a set with the numbers which are referred as an interval.

Suppose, We have 8 numbers in a list the at first we make an internal interval with 5 elements, This interval is also calculated by Knuth’s formula which is as follows.
h=h x 3 + 1 where h is an interval with starting value 1.

After making an interval we compare interval value with its set made and if it is smaller than interchanged position else not.
Again in the further pass, this process is followed until only 1 interval between the numbers is present.

In the end, we apply the Bubble sort on this number and finally, we got shorted list array by Shell sort.

Let’s see Shell sort in Data Structure example

Shell sort Example

Consider the following unsorted list & short this list with shell sort technique.
As the given number, we first found the interval between them (calculate the interval with a maximum number) as there is 8 number we consider a 5 as an interval spacing between numbers.
(Note: – select interval with odd numbers as 3, 5, 7, 9, 11 and make internal with the maximum number as much as possible because it makes easy to implement and sort list as fast as possible)

Interval 1:-

Shell Sort in Data Structure
Shell Sort

Interval set: {75, 24} {35, 64} {42, 57}
Now compare 75 & 24, 75>24, therefore, we swap the numbers so that the so that small number will come to its place.
Similarly, compare, the 35 < 57 not do anything and compare 42 < 75 not do anything we will get after the first interval.
24 35 42 13 75 64 57

Interval 2:-

Shell Sort in Data Structure
Shell Sort

Make interval as above, In the previous interval, we made an interval with the 5 now make an interval less than 5 (which is odd) is 3.
Interval set: {24, 13} {35, 87} {42, 75} {87, 57} {35, 87, 57} {42, 75}
Now compare this sets and arrange in a particular order as above.
24 > 13, swap the number we get 13 24.
35 < 87 > 57, We get 35 57 87
42 < 75, Not do anything.
Now arrange list, We get
13 35 42 24 57 75 64 87

Interval 3:-

Shell Sort in Data Structure
Shell Sort

Now, as interval 1 left so perform by taking 1 (Bubble sorting technique)
Sorted array – 13 24 35 42 57 64 75 87

Shell Sort algorithm

  1. Initialize the value of interval.
  2. Divide the list into smaller sub-list of equal interval.
  3. Sort these sub-lists using insertion sort.
  4. Repeat until complete list is sorted

Flowchart for Shell sort

Flowchart for Shell Sort
Flowchart for Shell Sort

Shell sort program in c

#include<stdio.h>
void ShellSort(int a[], int n)
{
int i, j, increment, tmp;
for(increment = n/2; increment > 0; increment /= 2)
{
for(i = increment; i < n; i++)
{
tmp = a[i];
for(j = i; j >= increment; j -= increment)
{
if(tmp < a[j-increment])
a[j] = a[j-increment];
else
break;
}
a[j] = tmp;
}
}
}

int main()
{
int i, n, a[10];
printf("Enter the number of elements :");
scanf("%d",&n);
printf("Enter the elements : ");
for(i = 0; i < n; i++)
{
scanf("%d",&a[i]);
}
ShellSort(a,n);
printf("The sorted elements are : ");
for(i = 0; i < n; i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}

Output:

Shell Sort

The complexity of shell sort

The time complexity for shell sort
The worst-case and average-case complexity for shell sort: O(((nlog(n))^2).
The Best case complexity of shell sort: O(n).
Space complexity for shell sort: O(1)

Advantages of shell sort

  • Shell Sort is based on Insertion sort.

Disadvantages of shell sort

  • The technique is difficult to understand and implement.
  • It requires more space.
  • The two different methods applied for sorting.
  • It is not much efficient.

Write A Comment