Shell Sort.














































Shell Sort.



C++ Shell Sort

(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 -

  1. Insertion Sort
  2. Bubble Sort
  3. Selection Sort
  4. Quick Sort
  5. Merge Sort
  6. Shell Sort( we will be discussing this)
This article will be divided in two parts
  1. Basic Definition, Theory and Idea.
  2. Implementation.
So, let's start our discussion.

Basic Definition, Theory and Idea

Shell Sort sometimes also referred as Diminished Increment sort, It uses Insertion Sort but, 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 every hth element produces a sorted list. Such a list is said to be h-sorted. 
Step-by-step visualisation of Shellsort
   ShellSort (Source : WikiPedia)

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 
9, 8, 7, 6, 5, 4, 3, 2, 1
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.gif
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.

Implementation

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;
}
}
}
}

To understand this clearly take this example

8 7 6 5 4 3 2 1

PASS 1 - Here when gap is (n/2) = (8/2) = 4, then we get these sublists

(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

PASS 2 - Here gap is 4/2 = 2

resulting list -

2 1 4 3 6 5 8 7

PASS 3 - Here gap is 2/2 = 1

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 n passes in insertion sort, 

References - 


Comments