# Shell Sort C Code And Algorithm

Shell sort is an in-place comparison sort. Donald Shell published the first version of this sort in 1959. It generalizes an exchanging sort, such as insertion or bubble sort, by starting the comparison and exchange of elements with elements that are far apart before finishing with neighboring elements. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange.

Shellsort is a multi-pass algorithm. Each pass is an insertion sort of the sequences consisting of every h-th element for a fixed gap h (also known as the increment). This is referred to as h-sorting. Shell sort is unstable,that is, it may change the relative order of elements with equal values.

It has "natural" behavior, in that it executes faster when the input is partially sorted.

 Shell Sort In Action

## Algorithm/Pseudo-Code:

Using Marcin Ciura's gap sequence, with an inner insertion sort.
```/* Double-Click To Select Code */
# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]

foreach (gap in gaps)
{
# Do an insertion sort for each gap size.
for (i = gap; i < n; i += 1)
{
temp = a[i]
for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
{
a[j] = a[j - gap]
}
a[j] = temp
}
}
```

## Here is the C Code for Shell Sort:

```/* Double-Click To Select Code */

#include <stdio.h>
#include <conio.h>
#define MAX 20

void main()
{
int arr[MAX],i,j,k,n,increment;
clrscr();
printf("Enter the number of elements: ");
scanf("%d",&n);
printf("\nEnter %d elements : \n",n);
for(i=0 ; i<n ; i++)
scanf("%d",&arr[i]);

printf("\nUnsorted list is:\n");
for (i = 0; i < n; i++)
{
printf("%4d",arr[i]);
}
increment=5;

/*ACTUAL LOGIC STARTS*/

while(increment>=1)
{
for(j=increment ; j<n ; j++)
{
k=arr[j];
for(i = j-increment ; i >= 0 && k<arr[i] ; i = i-increment)
arr[i+increment]=arr[i];
arr[i+increment]=k;
}
increment=increment-2;  /*Decrease the incrementement*/
}
printf("\n\nSorted list is:\n");
for (i = 0 ; i<n ; i++)
{
printf("%4d",arr[i]);
}
printf("\n\n *WWW.CODINGBOT.NET*");
getch();
}```

## Output of Program:

Please Comment If You Liked This Post !!