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….