Shell Sort

Shell Sort

This method is a improvement over the simple insertion sort. In this method the elements at fixed distance are compared. The distance will then be decremented by some fixed amount and again the comparison will be made. Finally, individual elements will be compared. Let us take some example.

Ex. 6.6.1: Sort the following list using shell sort.

Sol. :

Step 1:

Let us take the distance k = 5

So in the first iteration compare

(A [0], A[5])

(A [1], A [(6])

(A [2], A[7])

(A[3])

(A[4])

Step 2:

Initially k was 5. Take some d and decrement k by d. Let us take d = 2

k = k – d i.e. k = 5-2 = 3

So now compare

(A[0], A[3], A[6]), (A[1], A[4], A[7])

(A[2], A[5])

Step 3: Now k = k d   k = 3-2 = 1

So now compare

(A[0], A[1], A[2], A[3], A[4], A[5], A[6], A[7])

This sorting is then done by simple insertion sort. Because simple insertion sort is highly efficient on sorted file. So we get

Ex. 6.6.2 Sort the given integers and show the intermediate results using shell sort

35, 12, 14, 9, 15, 45, 32, 95, 40, 5

Sol. :

Step 1:

We will assume distance k = 5

Hence we will compare

(A[0], A[5])   i.e. 30 and 45

(A[1], A[6])   i.e.  12 and 32

(A[2], A[7])  i.e.   14 and 95

(A[3], A[8])  i.e.   9 and 40

(A[4], A[9])  i.e.  15 and 5    Exchange

The array will be

Step 2: Take some d. Let d = 2. Then set k = k-d.   k = 5-2 = 3

So now we will compare

(A[0], A[3], A[6], A[9])   i.e.   30, 9, 32, 15

(A[1], A[4], A[7])            i.e.    12, 5, 95

(A[2], A[5], A[8])            i.e.      14, 45, 40

The array then becomes as follows -

Step 3: Now k = k-d i.e. k = 3- 2 = 1

Now we will simply compare each element with every other element. The sorted list which we will get is

Ex. 6.6.3 C Program for sorting elements using shell sort.

Sol. :

/*************************************************************

Program for sorting the list of elements using shell sort

*************************************************************/

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define MAX 10

int main(void)

{

void shellsort(int a[], int n);

void Display(int a[], int n);

int a[MAX];

int i,n;

clrscr();

printf("\n\t Program for Shell Sort");

printf("\n Enter total number of elements in an array ");

scanf("%d", &n);

printf("\n Enter some elements in array\n");

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

scanf("%d",&a[i]);

printf("\nBefore sorting ");

Display(a,n);

printf("\n");

printf("\nAfter sorting ");

shellsort(a,n);

Display(a,n);

getch();

return 0;

}

void Display(int a[], int n)

{

int i;

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

{

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

}

}

void shellsort(int a[], int n)

{

int i,j,d,k,value;

d=(n+1)/2;

for(i=d;i>=1;i=i/2)

{

for(j=i;j<=n-1;j++)

{

value=a[j];

k=j-i;

while(k>=0 && value <a[k])

{

a[k+i]=a[k];

k=k-i;

}

a[k+i]= value;

}

}

}

Output

Program for Shell Sort

Enter total number of elements in an array 10

Enter some elements in array

10

9

8

7

6

5

4

3

2

1

Before sorting 10 9 8 7 6 5 4 3 2 1

After sorting 1 2 3 4 5 6 7 8 9 10

Review Question

1. State and explain the shell sort. State and explain the algorithm for shell sort. Sort the elements using shell sort.