Shell sort is a one of the sorting technique.
It is a rarely used technique as it seems difficult for implementing.
Shell sort is based on Insertion sort technique.
Shell sort technique
In this shell sort technique, We have a N number of list which are unsorted in this technique, We consider the N number in a list and depending upon that we make a set with the numbers which are referred as a interval.
Suppose, We have a 8 numbers in a list the at first first we make a internal interval with 5 elements, This interval is also calculated by Knuth’s formula which is as follows.
h=h x 3 + 1 where h is interval with starting value 1.
After making a intervals we compare interval value with its set made and if it is smaller then interchanged position else not.
Again in further pass this process is followed until only 1 interval between the numbers is present.
At the end, We apply the Bubble sort on this number and finally we got shorted list array by Shell sort.
Example:-
Consider the following unsorted list short this with Shell sort technique.
As given number, We first found the interval between them (calculate the interval with maximum number) as there are 8 number we consider a 5 as a interval spacing between numbers.
(Note:- select interval with odd numbers as 3, 5, 7, 9, 11 and make internal with the maximum number as much as possible because it make easy to implement and sort list as fast as possible)
Interval 1:-
Interval set:- {75, 24} {35, 64} {42, 57}
Now compare 75 & 24, 75>24 therefore we swap the numbers so that the so that small number will come to it’s place.
Similarly compare, the 35 < 57 not do anything and compare 42 < 75 not do anything we will get after first interval.
24 35 42 13 75 64 57
Interval 2:-
Make interval as above, In previous interval we made an interval with the 5 now make a interval less than 5 (which is odd) is 3.
Interval set:- {24, 13} {35, 87} {42, 75} {87, 57} {35, 87, 57} {42, 75}
Now compare this sets and arrange in a particular order as above.
24 > 13, swap the number we get 13 24.
35 < 87 > 57, We get 35 57 87
42 < 75, Not do anything.
Now arrange list, We get
13 35 42 24 57 75 64 87
Interval 3:-
Now, as interval 1 left so perform by taking 1 (Bubble sorting technique)
Sorted array – 13 24 35 42 57 64 75 87
Time complexity for shell sort is O(n).
Advantages of shell sort
- It based on Insertion sort.
Disadvantages of shell sort
- Difficult to understand and implement.
- Requires more space.
- Two method applied for sorting.
- Not efficient.
Program:-
| 123456789101112131415161718192021222324252627282930313233343536 | #define max20void main(){int arr[max],i,j,k,incr,n;printf(“Enter a number of element:”);scanf(“%a”,&n);for(i=0;i<n;i++){printf(“Enter element %d”,i+1);scanf(“%d”,&arr[i]);}printf(“Enter max increament code value:”);scanf(“%d”,&incr);while(incr>=1){printf(“\n increament: %a”, incr);for(j=incr;j<n;j++){k=arr[j];for(i=j-incr;i>=0 && k<arr[i];i=i-incr){arr[i=incr]=arr[i];}arr[i+incr]=k;}printf(“Increament %d “, incr);incr=incr-2;}printf(“Sorted List:”);for(i=0;i<n;i++){printf(“%d”,a[i]);}} |
Output:-
Enter element : 75 35 42 13 81
Sorted List : 13 35 42 75 81