Home | | **Fundamentals of Data Structures in C** | | **Data Structures** | | **Programming and Data Structures I** | 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).

**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_{1}, h_{2}, …_{t},calledhthe ** increment
sequence**. Any increment

sequence is fine as long as h_{1}
= 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}
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:**

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.