Invented by Donald Shell in 1959, Shell sort is the most efficient of the O(n2) class of sorting algorithms. It is also the most complex of the O(n2) algorithms. This algorithm is similar to bubble sort in the sense that it also moves elements by exchanges.

Shell sort begins by comparing elements that are at distance d. With this, the elements that are quite away from their place will move more rapidly than the simple bubble sort.

In each pass, the value of d is reduced to half.

In each pass, each element is compared with the element that is located d indexes away from it, and an exchange is made if required. The next iteration starts with a new value of d.

The algorithm terminates when d=1.

Example:

12

9

-10

22

2

35

40

Let us consider the starting value of d to be half the number of elements. d = n/2 = 7/2 = 3

Shell sort part 1 Shell sort part 2 Shell sort part 3

Analysis of Shell Sort

  1. It is difficult to predict the complexity of Shell sort, as it is very difficult to show the effect of one pass on another pass.
  2. One thing is very clear that if the new distance d is computed using the above formula, then the number of passes will approximately be log2d since d=1 will complete the sort.
  3. Empirical studies have shown that the worst case complexity of Shell sort is O(n2).

C/C++ Implementation

.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; } .cb3 { color: maroon; }

void shellsort(int a[], int n)
{
 int d, temp, i;
 d=n/2;
 while (d>=1)
 {
 for (i=0;i<n-d;i++)
 {
 if (a[i]>a[i+d])
 {
 temp=a[i];
 a[i]=a[i+d];
 a[i+d]=temp;
 }
 }
 if(d==1)
 return;
 d=d/2.0+0.5;
 }
}

Complete Program

/**
 * Shell Sort
 * http://www.byteguide.com
 */
 
#include <stdio.h>
 
void shellsort(int [], int );
 
int main()
{
 int a[50], n, i;
 printf("How many elements do you want to create the array with?"
 "(max 50): ");
 scanf("%d", &n);
 fflush(stdout);
 puts("Enter the array elements");
 for (i=0; i<n; i++)
 scanf("%d", &a[i]);
 shellsort(a, n);
 puts("--------Sorted Array--------");
 for (i=0; i<n; i++)
 printf("%dn", a[i]);
 printf("n");
 
 return 0;
}
 
void shellsort(int a[], int n)
{
 int d, temp, i;
 d=n/2;
 while (d>=1)
 {
 for (i=0;i<n-d;i++)
 {
 if (a[i]>a[i+d])
 {
 temp=a[i];
 a[i]=a[i+d];
 a[i+d]=temp;
 }
 }
 if(d==1)
 return;
 d=d/2.0+0.5;
 }
}

Output

How many elements do you want to create the array with?(max 50): 6 Enter the array elements 3 67 85 89 56 44 ——–Sorted Array——– 3 44 56 67 85 89