## Shell Sort

Back to Programming

### Description

Shell sort is a comparison-based sorting technique in which the elements of a particular distance (or gap) are compared with each other and according to the order of sorting their values are swapped

It is different from a bubble or selection sort. It is an in-place sorting algorithm where no extra memory space is required to sort the data. After each pass of sorting the gap is reduced and the sorting continues till the gap between the two elements reaches 0

The gap between two elements decreased depending on the sequence used to sort. The original sequence of gapping is n/2, n/4, n/8, ….., 1 where n is the number of elements of the array. There are some other sequences also which can be used to sort the elements. They are:

1. Knuth’s increments: 1, 4, 13, …, (3k – 1) / 2

2. Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81....

3. Sedgewick’s increments: 1, 8, 23, 77, 281, 1073, 4193, 16577...4j + 1+ 3·2j + 1.

4. Papernov & Stasevich increment: 1, 3, 5, 9, 17, 33, 65,...

5. Hibbard’s increments: 1, 3, 7, 15, 31, 63, 127, 255, 511…

PROCEDURE WITH EXAMPLE:

Suppose there is an array that has 8 elements as follows:

The array should be sorted in ascending order. In this sorting, the original sequence of gapping is used i.e. n/2 , n/4, n/8, … , 1

So here n=8 (total number of elements)

## Pass 1:

For the first pass the gap= n/2 = 8/2 = 4

So, first the first element of the array i.e. 56 is compared with the element at index 4, here the element is 43. As 43 is lesser than 56 so, swapping required and 56 will be stored at index 4 of the array. And as the interval is 4 so no other element is there to compare so 43 will be stored at 0th position and the array will be:

Now, the second gap is n/4 = 8/4 =2 similarly 78 will be compared with 12 and as 12 is lesser than 78 they will also be swapped and the array will be:

Here, between 34 and 69, 34 is already lesser than 69 so there will be no swapping. So the array will remain unchanged.

Now, the last pair i.e. 67 and 54 will be compared and will be swapped and after 1st pass we will get the array:

## Pass 2:

In the second pass, the gapping is n/4 = 8/4 = 2

Before the 2nd pass the array is:

First, 43 is compared to 34. As 34 is lesser than 43 so it will be swapped. And the array will be:

12 and 54 will be compared next but as there is no swapping the array will remain same.

This step will be a little different from the previous steps. In this step 56 and 43 will be compared first (i.e. index 4 and index 2) here no change will be performed but again 43 will be compared with 34 (i.e. index 2 with index 0), as 34 is also lesser than 43 so there will be no change. That means all the elements of the array of the same interval from right to left will be compared in a similar way so the array will remain the same.

Here also 78 will be compared to 54 and again 54 will be compared to 12. But as they are incorrect order so there will be no change.

In this step 69 will be compared with 56, 56 will be compared with 43, and 43 will again be compared with 34, all these elements are in the correct order so there will be no change.

Firstly 67 is compared with 78, as 67 is lesser than 78 so it will be swapped. Now 67 will be compared to 54 but as 67 is greater than 54 so there will be no swapping. The 67 will be placed at the position of 78 and the array will be:

## Pass 3:

Here the gap is: n/8= 8/8 = 1. So here the adjacent elements will be compared.

Before starting the sorting the array is:

Here, 34 will be compared to 12. As 12 is lesser than 34, it will be swapped. After swapping the array will be:

Here, 43 will be compared to 34, and 34 will be compared to 12. As they are in the correct order so there will be no change.

Here also the array is already in sorted order. Similarly in the next steps, the array elements will be compared by the following steps:

### Algorithm

``````INPUT: An unsorted array a[6,2,4,1,…………….,n]
OUTPUT: An sorted array a[1,2,3,4,5,…………..,n] (in ascending order)
PROCESS:
Step 1: [Taking the inputs from the user]
for i=0 to n repeat
Step 2: [Sorting the elements using shell sort]
Set step<-n/2
While step>0 repeat
For i=step to n repeat
Set tmp<-arr[i]
For j=i to j>=step and  arr[j-step]>tmp repeat
Set arr[j]<-arr[j-step]
Set j<-(j-step)
Set arr[j]<-tmp
Set step<-step/2
Step 3: [Displaying the array elements]
For i=0 to n repeat
Print arr[i]
Step 4: Stop.
``````

### Code

CHARACTERISTICS:

1. This is a comparison based sorting technique.

2. This sorting is done by comparing the elements at a particular interval.

3. This is an in-place sorting algorithm, no extra space is needed to sort the data.

4. It is a highly efficient sorting algorithm.

5. Shell sort is not a stable sort.

TIME COMPLEXITY:

The time complexity of the shell sort depends on the sequence of gapping used in the sorting technique.

Here, the original sequence of shell sort i.e. n/2, n/4, n/8, ….. , 1 is used as a gapping sequence to sort the elements of the array. Hence in the best case the number of comparisons in each interval will be:    The average case complexity is also O(n*logn) in a similar way as the best case.

The worst case of shell sort occurs when the elements are totally in the opposite order. So for n number of elements, the last pass will be working as the bubble sort. But this complexity depends on the sequence used to sort the data.

SPACE COMPLEXITY:

Space complexity of shell sort is O(1) as it does not require any extra space to sort the data.

APPLICATION:

1. A shell sort can be implemented using a small code, it is used in some applications to sort data instead of using the quick sort.

2. It can also be used to sort a subarray in some other sorting techniques to reduce the time and make the sorting faster.

1. The code is smaller than quick sort, merge sort, or heap sort.

2. It does not use any additional memory space.

3. The performance of shell sort is decent in worst case also.

4. It is faster than bubble sort and insertion sort.