Shell Sort Algorithm

An inventor called DL Shell came up with a very interesting sort which he called shell sort. This sorting algorithm is almost similar to the bubble sort algorithm. The shell sort compares elements that are a certain distance away (d positions away) from each other and it compares these elements repeatedly (bubble sort only compares adjacent elements.) It uses the equation d = (n + 1) / 2.

The comparison model makes the sorting process of the shell sort very efficient.

Take a look at the shell sorting example:


#include<iostream>
using namespace std;

int main(void)
{
	int array[5];		// An array of integers.
	int length = 5;		// Length of the array.
	int i, d;
	int tmp, flag;

	//Some input
	for (i = 0; i < length; i++)
	{
		cout << "Enter a number: ";
		cin >> array[i];
	}

	//Algorithm
	d = length;
	flag = 1;
	while ( flag || (d > 1))
	{
		flag = 0;
		d = (d + 1)/2;
		for (i =0; i < (length - d); i++)
		{
			if (array[i + d] > array[i])
			{
				tmp = array[i+d];
				array[i + d] = array[i];
				array[i] = tmp;
				flag = 0;
			}
		}
	}

	//Some output
	for (i = 0; i < 5; i++)
	{
		cout << array[i] << endl;
	}
}


In the comment section Siddhartha Gupta made the comment that the “flag” variable was not needed as in the example above. He replaced the construction with a do-while loop. So we made the changes he suggested and below you will find the result:


#include<iostream>
using namespace std;

int main(void)
{
	int array[5];		// An array of integers.
	int length = 5;		// Length of the array.
	int i, d;
	int tmp;

	//Some input
	for (i = 0; i < length; i++)
	{
		cout << "Enter a number: ";
		cin >> array[i];
	}

	//Algorithm
	d = length;
	do {
		d = (d + 1)/2;
		for (i =0; i < (length - d); i++)
		{
			if (array[i + d] > array[i])
			{
				tmp = array[i+d];
				array[i + d] = array[i];
				array[i] = tmp;
			}
		}
	} while(d > 1);
	
	//Some output
	for (i = 0; i < 5; i++)
	{
		cout << array[i] << endl;
	}
}


He also requested to change the order from descending to ascending. This can easily be done by changing one statement.
In the do-while loop the following statement makes the sort in descending order:


if (array[i + d] > array[i]) // greater than for descending order

In the do-while loop, replace the statement for ascending order with this:


if (array[i + d] < array[i]) // less than for ascending order

That is all for this tutorial.

This entry was posted in Programming Algorithms. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed. Tweet This! Tweet This! or use to share this post with others.

There are currently 17 responses to “Shell Sort Algorithm”

Why not let us know what you think by adding your own comment!

  1. pranav asthana on November 8th, 2009:

    very helpfull indeed thanks!

  2. Siddhartha gupta on May 28th, 2010:

    Thanks very helpful indeed…this sorts in descending order though 🙂
    Also, an unrequired ‘j’ has been declared

  3. Siddhartha gupta on May 28th, 2010:

    Also,I was wondering the use of flag? ..I’m assuming it has been used just to make sure that the loop runs atleast once..though we can use a do-while loop to do the same right?
    I did that and it worked 😉

  4. admin on June 1st, 2010:

    Removed the unused variable j from the example, thanks for that!
    Also added the changes you suggested, you can see them now in the tutorial.

  5. Connie on June 22nd, 2010:

    is it posible to apply shell sort in guest book???? help…

  6. rica palmagil on December 10th, 2010:

    thank you so much! it help me all the way..=)

  7. nasios on January 23rd, 2011:

    How can I convert this algorithm for emu8086?

  8. Ann Ghie on March 15th, 2011:

    tnx….

  9. Parthi on February 13th, 2012:

    It’s very very nice and easily understand the logic….

    thnks & superup……

  10. jubin on October 20th, 2012:

    this program is not working when we put the values 75,25,35,15,85,5,95,45 and length is changes as 8..

  11. admin on October 21st, 2012:

    @jubin: The programs are working fine, but you have to input the same number of digits, so 5 becomes 05 if the rest are also two digits integers. Take a look at my test output.

    First with all two digits integers:
    C:\Projects\next\Debug>next
    Enter a number: 75
    Enter a number: 25
    Enter a number: 35
    Enter a number: 15
    Enter a number: 85
    Enter a number: 95
    Enter a number: 45
    Enter a number: 65
    95
    85
    75
    65
    45
    35
    25
    15

    Then with your input numbers, 5 becomes 05:
    C:\Projects\next\Debug>next
    Enter a number: 75
    Enter a number: 25
    Enter a number: 35
    Enter a number: 15
    Enter a number: 85
    Enter a number: 95
    Enter a number: 05
    Enter a number: 45
    95
    85
    75
    45
    35
    25
    15
    5

  12. yared on January 7th, 2013:

    very interesting …….site

  13. RIturaj on July 2nd, 2013:

    The second program wont work for even number of elements.. in case you need it for even number of sample size use only hte first one

  14. Praveena on August 1st, 2013:

    yeah.. what jubin said is correct…@admin check with the exact sequence which he gave.. also, see dis one..
    with length as 8,

    Enter a number: 9
    Enter a number: 1
    Enter a number: 8
    Enter a number: 2
    Enter a number: 7
    Enter a number: 3
    Enter a number: 6
    Enter a number: 4
    9
    8
    4
    7
    3
    6
    2
    1
    ..

  15. Praveena on August 1st, 2013:

    i guess one more iteration with distance as 1(d=1) is needed..

  16. sonu kumar on October 8th, 2013:

    thnx bro, i love u…
    really very helpfull for us…

  17. Kiko on February 17th, 2014:

    Just a question: Why do you use flag controlled loop? What will be the reason that obstructs swapping of the elements?- The reason to use the flag is to confirm swapping I suppose.