**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 the **Insertion sort** technique.

## Shell sort technique

In this shell sort technique, We have an **N** number of a list which is 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 an interval.

Suppose, We have 8 numbers in a list the at first we make an 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 an interval we compare interval value with its set made and if it is smaller then interchanged position else not.

Again in the further pass, this process is followed until only 1 interval between the numbers is present.

In 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 list with shell sort technique.

As the given number, We first found the interval between them (**calculate the interval with a maximum number**) as there is 8 number we consider a 5 as an 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 makes 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 its place.

Similarly, compare, the 35 < 57 not do anything and compare 42 < 75 not do anything we will get after the first interval.

**24 35 42 13 75 64 57**

**Interval 2:**

Make interval as above, In the previous interval, we made an interval with the 5 now make an 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**

The 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 methods applied for sorting.
- Not efficient.

## Shell sort program in c

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#define max20 void 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**

## Leave a Reply