## Introduction

This article can be considered as the continutation of the article explaining Insertion Sort. To have a quick look please visit Insertion Sort. In this article we will learn how to over come the limitations of Insertion Sort by understanding the Basics of Shell Sort. You can also consider Shell Sort to be an improvement over Insertion Sort.

## Purpose of the article

To understand the Basics of Shell Sort and compare it with insertion sort. We will also write code snippets and pseudo codes to understand it better.

## Idea behind Shell Sort

The biggest limitation of Insertion Sort is when the input is reverse sorted or nearly reverse sorted. Shell sort tries to optimize that part and hence removes that drawback. There are various ways to explain it, here I try to explain it in the simplest possible manner.

We take an example of input which is reverse sorted.

We define a gap size or an increment size for each iteration of Shell Sort. At the very first iteration we define the gap size to be half of the length of input i.e. L/2. In our case, that would be 8/2 = 4.

In iteration 1 the gap size equals to 4.

We need the gap size to identify groups of element which can be individually sorted and merged to form a bigger group. This no where guarantees that the bigger group formed will be fully sorted but it will definitely create localized sorted groups.

Lets understand this with an example using the above input array.

We have gap size as 4 means we will create groups of four elements each

Now we try to sort elements in each **column** above using Insertion Sort. As the elements would be lesser in number compared to the complete array, it will be a better idea to sort them columnwise. After iterating through each column the groups will change to following:

Now append the elements from group 2 to the elements of group 1.

Final array after iteration 1 is :

Now we decrease the gap size by 1 , gap size = 4-1 = 3

Repeat the same procedure:

Now we try to sort elements in each column above using Insertion Sort. After iterating through each column the groups will change to following:

Now append the elements from group 2 and 3 to the elements of group 1.

Final array after iteration 2 is :

Now we decrease the gap size by 1 , gap size = 3-1 = 2

Repeat the same procedure:

Now we try to sort elements in each column above using Insertion Sort. After iterating through each column the groups will change to following:

Now append the elements from group 2 , 3 and 4 to the elements of group 1.

Final array after iteration 3 is :

Now we decrease the gap size by 1 , gap size = 2-1 = 1

Hence no point dividing it in groups. Now run the whole array through insertion sort. It will take lesser time to complete compared to the time taken by isnertion sort in the original input array.

Final array after iteration 3 is :

# Analysis by example

Lets find out if this was really better.

We will count the total number of comparisons, swaps and shifting required by both the sorting techniques to find out which is better.

**Insertion Sort**

Input – 9——-7——-5——-4——-3 ——-2——-1——-0.

Intermittent array states:

3——-2——-1——-0——-9——-7——-5——-4 – comparison 1—swap 1— shifting 1

5——-7——-9——-4——-3——-2——-1——-0 – comparison 2—swap 1— shifting 2

4——-5——-7——-9——-3——-2——-1——-0 – comparison 3—swap 1— shifting 3

3——-4——-5——-7——-9——-2——-1——-0 – comparison 4—swap 1— shifting 4

2——-3——-4——-5——-7——-9——-1——-0 – comparison 5—swap 1— shifting 5

1——-2——-3——-4——-5——-7——-9——-0 – comparison 6—swap 1— shifting 6

0——-1——-2——-3——-4——-5——-7——-9 – comparison 7—swap 1— shifting 7

Total – comparisons – 28 , shifting 28 , swaps – 7

**Shell Sort**

Input – 9——-7——-5——-4——-3 ——-2——-1——-0.

Intermittent array states

7——-9——-5——-4——-3——-2——-1——-0 – comparison 4—swap 4— shifting 0

0——-2——-1——-3——-4——-7——-5——-9 – comparison 7—swap 2— shifting 0

0——-2——-1——-3——-4——-7——-5——-9 – comparison 12—swap 0— shifting 0

0——-1——-2——-3——-4——-5——-7——-9 – comparison 9—swap 2— shifting 2

Total – comparisons – 32 , shifting 2 , swaps – 8

If you closely see then we could have avoided the third iteration in Shell Sort just by keeping a track of how many swaps happened in a given iteration and if the swap count is zero we can straight away move to the final iteration.

The result will significantly improve and the new total will be as follows:

Total – comparisons – 20 , shifting 2 , swaps – 8

Which I find to be a significant improvement.

## Code and Implementation

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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
package com.test; public class ShellSort { public static void main(String[] args) { int[] a = new int[] { 9, 7, 5, 4, 3, 2, 1, 0 }; ShellSort ss = new ShellSort(); System.out.println("Input array - "); ss.printArray(a); ss.shellSort(a); System.out.println("Sorted array - "); ss.printArray(a); } public void shellSort(int[] a) { int gap = a.length / 2; int swapped = 1; while (gap > 1 && swapped != 0) { swapped = 0; int[] indices = new int[a.length / gap]; for (int i = 0; i < gap; i++) { int k = 1; indices[0] = i; for (int l = i; k < indices.length; l++) { indices[k] = indices[k - 1] + gap; k++; } swapped += sortByPositions(a, indices); } gap--; } insertionSort(a); } // custom code which sorts elements which are at specified indices in an array and returns if there was any swap involved. public int sortByPositions(int[] a, int[] indices) { int l = indices.length; int swapped = 0; for (int j = 1; j < l; j++) { int key = a[indices[j]]; int i = j - 1; while (i >= 0 && a[indices[i]] > key) { a[indices[i + 1]] = a[indices[i]]; i = i - 1; } a[indices[i + 1]] = key; swapped++; } return swapped; } //plain insertion sort code. public void insertionSort(int[] a) { for (int j = 1; j < a.length; j++) { int key = a[j]; int i = j - 1; while (i >= 0 && a[i] > key) { a[i + 1] = a[i]; i = i - 1; } a[i + 1] = key; } } public void printArray(int[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } System.out.println(); } } |

## Conclusion

For more on Shell Sort please visit wikipedia.

Shell sort is simply an improvement over the insertion sort. It’s running time is better than Insertion Sort in average cases.

Stay connected and stay Subscribed

[do_widget “Blog Subscriptions (Jetpack)”]