Basics of Shell Sort

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.

Input – input-ss

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

group-ss-1

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:

groups-ss-2

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

Final array after iteration 1 is : input-2-ss

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

Repeat the same procedure:

group-ss-3

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

group-ss-4

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

Final array after iteration 2 is : input-3-ss

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

Repeat the same procedure:

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

group-ss-6

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

Final array after iteration 3 is : input-4-ss

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 : input-5-ss

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

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)”]

  • Maheshwar Reddy

    Hi,
    I have implemented a method for the Shell Short.
    This method uses the same logic explained as above.

    static void shell_sort(int arr[])
    {
    int gap,j,k,l,len,key;
    len = arr.length;
    gap = (len+1)/2;
    while(gap>=1)
    {
    for(j=0;j<=gap-1;j++)
    {
    for(k=j+gap;k=j;l=l-gap)
    {
    if(arr[l]>key)
    arr[l+gap]=arr[l];
    else
    break;
    }
    arr[l+gap]=key;
    }
    //System.out.println();
    }
    for(int a:arr)
    {
    System.out.print(a + ” “);
    }
    System.out.println();
    gap–;

    }

  • dharam

    Hi,

    Thanks for the code, I have not tested it, hope it works fine…

    Moreover, in my code I wrote one extra method just to show that we can also sort only given indexes in an array 🙂

  • Maheshwar Reddy

    Hi Dharam,
    I have tested my code, it is working fine.
    And I don’t know how to calculate the Time & Space complexities.
    Can you please tell me how to calculate….?
    OR if you are going to post a new article for calculating those… it would help us….
    THANK YOU.. 🙂

  • dharam

    Yeah sure… I will write an article on how to find the running time of an algorithm.. I believe I have already written one to teach the basics of running time and how is it derived. Please check http://techieme.in/techieme/analysis-of-algorithms-made-easy/