Shell Sort

Given an array of integers and aim is to sort that array in ascending/descending order using shell sort algorithm.

Shell Sort is an interesting sorting algorithm that works on top of insertion sort. But here in this algorithm the insertion intervals are not continuous. This interval will be defined based on a formula.

Formula:
[latex display="true"]n = n * 3 + 1[/latex]
here "n" (interval) is nearly equal to input array length / 3.

There can be many formulas for this (which is 2^n ), but above mentioned is the most popular and optimized formula to use in shell sort algorithm. Let’s take below example input/output and understand it with step-by-step illustration.

Example:
Input: {4, -10, 11, 9, 41, 16, 5}
Output: {-10, 4, 5, 9, 11, 16, 41}
Above output is in ascending sort order.

Step by step guide

4-1011941165

Here the interval is 4, so we need to compare {4,41}, {-10,16} and {11,5}.

4-1059411611

As 11 > 5, so those two items swapped as shown above.

Now the interval becomes 4/3 which is 1, below are all illustrations with interval 1.

4-1059411611

As -10 < 4, 4 moved right to -10, as shown in right side array.

-10459411611
-10459411611

As 5 > 4, Keep as it is, as shown in right side array.

-10459411611
-10459411611

As 9 > 5, Keep as it is, as shown in right side array.

-10459411611
-10459411611

As 41 > 9, Keep as it is, as shown in right side array.

-10459411611
-10459411611

As 16 < 41, move 41 to right side of 16, as shown in right side array.

-10459164111
-10459164111

As 11 < 16, move both the elements to right side of 11, as shown in right side array.

-10459111641

It seems like this algorithm is an extension of insertions sort. But for large input arrays this shell sort algorithm gives better runtime performance than normal insertion sort. Now it is time to code the algorithm.

Code

#include <iostream>

using namespace std;

void printArray(int inp[], int len)
{
	for(int i=0; i<len; i++)
		cout<<inp[i]<<" ";
	cout<<endl;
}

int calcInterval(int len)
{
	int result = 0;
	while(result < len / 3)
		result = result * 3 + 1;
	return result;
}

void shellSort(int inp[], int len)
{
	int interval = calcInterval(len);

	for(; interval > 0; interval /= 3)
	{
		for(int j=interval; j<len; j++)
		{
			int temp = inp[j];
			int k;
			for(k=j; k>=interval &&
			 	inp[k-interval] > temp;
				k -= interval)
			{
				inp[k] = inp[k-interval];
			}
			inp[k] = temp;
		}
	}
	
}

int main(int argc, char* argv[])
{
	int inp[] = {4, -10, 11, 9, 41, 16, 5};
	int len = sizeof(inp) / sizeof(inp[0]);
	
	cout<<"Input Array: "<<endl;
	printArray(inp, len);
	shellSort(inp, len);
	cout<<"Sorted Array: "<<endl;
	printArray(inp, len);

	return 0;
}
Output:
Input Array: 
4 -10 11 9 41 16 5 
Sorted Array: 
-10 4 5 9 11 16 41

Complexity: [latex display="true"]O(n^2)[/latex]
Space: [latex display="true"]O(1)[/latex]

Though this algorithm has a similar complexity as insertion sort. But for long input arrays the algorithm performs better. This is the end of the shell sort algorithm. If you observe any problems with algorithm or code, please let readers know by commenting below. Cheers!.

Advertisements