(Pre-requisite - **Insertion Sort**)

Shell Sort is one of the Sorting techniques which uses Comparisons to perform its function, Other Sorting techniques which uses comparisons are -

**Insertion Sort****Bubble Sort****Selection Sort****Quick Sort****Merge Sort****Shell Sort( we will be discussing this)**

This article will be divided in two parts

- Basic Definition, Theory and Idea.
- Implementation.

So, let's start our discussion.

Shell Sort sometimes also referred asDiminished Increment sort, It usesInsertion Sortbut, with some optimizations. The intuitive Optimization is : It divides the Main array/list in smaller lists and perform insertion sort on each of those list, to sort them. The idea is to arrange the list of elements so that, starting anywhere, taking everyhthelement produces a sorted list. Such a list is said to beh-sorted.

Now, let's see how Insertion sort helps in accomplishing the Shell Sort, and what optimization does Shell Sort Performs,

Let's try to explain the same with the following example

Suppose we have a given list

and we want to sort it in non increasing order using Insertion Sort.

Below is the implementation of the Insertion Sort.

void InsertionSort(int arr[], int n){

for(int i = 0; i< n ;i++){

int j = i;

while(j > 0 && arr[j-1] > arr[j]) // <-- Take a look here

swap(arr[j], arr[j-1]);

}

}

For the simple input we considered above, the internal while loop in the algorithm will compare each element to every element occuring before it.

For e.g. if we are Index **5**, Index **5** element will be compared and swapped with each element before it i.e. indices ** 4, 3, 2, 1**. So, the number of comparison is very high.

Insertion Sort (Source - WikiPedia)

The Outer Loop executes **"n" **times, which makes our algorithm slower.

The benefit of **insertion sort** is that it, is **"Adaptive"**, i.e.

*If the array is already sorted, the number of comparisons will be only "n".*

And, as I already mentioned **Shell sort **uses insertion sort internally, it is also **Adaptive.**

Now, let's see, how Shell sort is optimized?

The Idea is dividing the main list into smaller sublists, and sort them using insertion sort, These sublists are often created using elements taken from the main array that are present in the array at some specified "Gap", and we will decrease the gap with each iteration we perform. Here I will be take the initial gap as floor(n/2) and dividing the gap by 2 with each iteration until gap becomes zero.

Following the Idea we discussed above, we can easily construct the algorithm as follows

Implementation -

void ShellSort(int arr[], int n) {

for (int gap = n / 2; gap > 0; gap /= 2) { // Decreasing gap with every iteration

for (int i = gap; i < n; i++) {

int temp = i;

while (temp - gap >= 0 && arr[temp - gap] > arr[temp]) { // Comparing values "gap" distance apart

swap(arr[temp - gap], arr[temp]);

temp -= gap;

}

}

}

}

**8 7 6 5 4 3 2 1**

(8, 4), (7, 3), (6, 2), (5, 1),each of which having a gap of 4 (in their indices)

The resulting list after first pass is

**4 3 2 1 8 7 6 5**

resulting list -

**2 1 4 3 6 5 8 7**

Resulting list -

**1 2 3 4 5 6 7 8**

So, here we get the sorted list here in just ** 3** passes whereas, we need

References -

Name | Views | Likes |
---|---|---|

C++ program to find Minimum of each subarrays in Linear Time. | 53 | 0 |

C++ Algorithm to find Path matrix of a graph. | 48 | 0 |

Implement BODMAS using C++. | 161 | 0 |

Shell Sort. | 222 | 0 |

3n+1 Problem Solution using C++. | 85 | 0 |

## Comments