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.
Tweet This! or use
to share this post with others.
very helpfull indeed thanks!
Thanks very helpful indeed…this sorts in descending order though 🙂
Also, an unrequired ‘j’ has been declared
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 😉
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.
is it posible to apply shell sort in guest book???? help…
thank you so much! it help me all the way..=)
How can I convert this algorithm for emu8086?
tnx….
It’s very very nice and easily understand the logic….
thnks & superup……
this program is not working when we put the values 75,25,35,15,85,5,95,45 and length is changes as 8..
@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
very interesting …….site
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
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
..
i guess one more iteration with distance as 1(d=1) is needed..
thnx bro, i love u…
really very helpfull for us…
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.