Shell Sort

                           SHELL SORT

Shell sort is one of the oldest sorting algorithm named after its inventor Donald L.Shell(1959).

It improves on the efficiences of insertion sort by quickly shifting values to their destination.

It is fast easy to understand and easy to implement.

Its complexity analysis is somewhat more sophisticated.

METHOD......

  • This method makes repeated use of insertion sort.
  • To sort n elements of an array by this method requires a number Si called increment or step should be chosen before every pass.
  • Si should be less than n.
  • For the last pass Si should be 1.
  • Initial value of step or increments can be n/2 and in further passes Si should be previous pass i.e.

S1 =n/2

S2 = S1/2

S3 = S2/2

.

.

.

.

.

.

Si+1 = Si/2

1st Pass

  • If an array a[0], a[1],..........a[7] has 8 elements then step or increment S1=8/2=4. Array will be divided into four sublists in the first pass i.e.
  • 1st sublist: (a[0], a[0+4])
  • 2nd   sublist: (a[1], a[1+4])
  • 3rd   sublist: (a[2], a[2+4])
  • 4th   sublist: (a[3], a[3+4])
  • These 4 sublists are sorted using inserion sort independently.

2nd Pass

  • In the second pass increment or step S2=S1/2=4/2=2.
  • Array will be divided into 2 sublists i.e.
  • 1st sublist: (a[0], a[0+2],a[0+4],a[0+6])
  • 2nd   sublist: (a[1], a[1+2],a[1+4],a[1+6])
  • These 2 sublists are sorted using insertion sort independently.

3rd Pass

  • In the third pass the value of step S3=S2/2=2/2=1.
  • Array will be divided into 1 sublists i.e.

1st sublist: (a[0], a[1],a[2].......a[7])

This sublist is sorted using insertion sort and we get all the elements in sorted form.

ALGORITHM.........

In this algorithm also array a is passed having the size n.

Shell(A,N)

{

For(s=n/2;s>0;s=s/2)

{

For(i=s;i<n;i++)

{

T=a[i];

For(j=i;j>=s;j=j-s)

{

If(t<a[j-s])

            A[j]=a[j-s]

Else

            Break

            }

            A[j]=t

}

}

}

EXPLANATION.......

Let’s take an example to sort the following elements using shell sort.

Array a[]=123 971 80 7 92 20 10 55

Original Array   123 971 80 7 92 20 10 55

1st pass

S1=8/2=4

  • Array before

123 971 80 7                       92 20 10 55

123 92

971 20

  1. 10
  2. 55

There are 4 sublists, each sublist has 2 elements, These are to be sorted using insertion sort method.

  • Array after

92 20       10 7        123 971           80 55

2nd pass

S2=S1/2=2

Array before

92 20 10 7 123 971 80 55

So there are 2 sublists, each sublist has 2 elements. There are to be sorted using insertion sort method.

Array after

10 7              92 20           80 55           123 971

3rd Pass

S3=S2/2=1

Array before

10 7 92 20 80 55   123 971

There is only one sublist of 8 elements. These are to be sorted using insertion sort method and we get all the elements in sorted order.

Array after

7 10 20 55 80 92 123 971

Program to sort n elements using shell sort method

#include<stdio.h>

#include<conio.h>

void shell(int [],int);

int a[100];

void main ()

{

int i,n;

clrscr();

printf("Enter the size of an array");

scanf("%d",&n);

printf("Enter %d elements of array",n);

for(i=0;i<n;i++)

scanf("%d",&n);

shell(a,n);

printf("\n Sorted list is::");

for(i=0;i<n;i++)

printf("%d\t",a[i]);

getch();

}

void shell(int a[],int n)

{

int i,j,s,t;

for(s=n/2;s>0;s=s/2)

{

for(i=s;s>0;s=s/2)

{

t=a[i];

for(j=i;j>=s;j=j-s)

{

if(t<a[j-s])

a[j]=a[j-s];

else

break;

}

a[j]=t;

}

}

}

 

 

OUTPUT.......

Shell Sorting in Data Structure