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.
• 1st 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 h1, h2, …t,calledhthe increment sequence. Any increment
sequence is fine as long as h1 = 1 and some other choices are better than others. We can choose the increment sequence with the following range,
#include<conio.h> h1 1 int main()
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++)
for(k=j; k>=i; k=k-i)
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.
Then the altered array will be as follows,
The resultant array is sorted now.
Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.