Shell sort

SHELL SORT

Shell sort, also known as the diminishing increment sort, is one of the oldest sorting algorithms, named after its inventor Donald. L. Shell (1959).

Founded by Donald Shell and named the sorting algorithm after him in 1959.

•      1^st algorithm to break the quadratic time barrier but few years later, a sub quadratic time bound was proven

•      Shell sort works by comparing elements that are distant rather than adjacent elements in an array or list where adjacent elements are compared.

•      Shell sort uses a sequence h₁, h₂,   …_t,calledhthe increment sequence. Any increment

sequence is fine as long as h₁ = 1 and some other choices are better than others. We can choose the increment sequence with the following range,

#include<stdio.h>

#include<conio.h> h₁ 1 int main()

{

int arr[30];

int i,j,k,tmp,num;

printf("Enter total no. of elements : "); scanf("%d", &num);

for(k=0; k<num; k++)

{

printf("\nEnter %d number : ",k+1); scanf("%d",&arr[k]);

}

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

{

for(j=i; j<num; j++)

{

tmp=arr[j];

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

{

if(tmp<arr[k-i])

{

arr[k]=arr[k-i];

}

else

{

break;

}

arr[k-i]=tmp;

}

}

}

printf("\t**** Shell Sorting ****\n");

for(k=0; k<num; k++) printf("%d\t",arr[k]);

getch(); return 0;

}

Execution of Algorithm:

For the Span value 5 the comparisons and swapping will be as follows

Now the comparison between 72 and 45 left value should be least value so 45 swapped to first location. Now the altered list was,

Then span 5 repeatedly compare following elements,

On these comparisons with span value 5 the elements 45 and 42 , 65 and 13 are get interchanged.

For SPAN=3

Then the altered array will be as follows, 

The resultant array is sorted now.

Complexity Analysis: