Sorting Algorithm 12: Shell Sort

In this chapter we shall learn about below topics:

Shell sort is also called as Diminishing increment sort, Comb sort, Gap sort invented by Donald L. Shell.

In this algorithm is based on comparison, but instead of comparing and swapping adjacent elements, it compares the elements that are having certain gap present between them.

Hence we shall sort the algorithm till the gap reduces to 1.

There are many ways that one can select the gap. Below are some of the ways of gap sequence are:

1. Original Sequence [N/2], [N/4] …. 1 recursively divide by 2.

2. Hibbard Sequence [1, 3, 7, 15 …. (2^k -1)]

3. Sedgewick Sequence [1, 8, 3, . . .]

In this example we shall use the Original Sequence.

We find the “gap” by using the formula “number_of_elements / 2”.

The example for shell sort will be discussed in Comb Sort Algorithm.

#include <stdio.h>
 
void shellSort(int arr[], int size) {
	int i, j, gap, temp;
 
	//we start with a bigger gap
	gap = size/2;
 
	while(gap > 0) {
		//now we will do the insertion sort of the gapped elements
		i = gap;
 
		while(i < size) {
			temp = arr[i];
 
			//shifting gap sorted element to correct location
			for(j = i; (j >= gap) && (arr[j - gap] > temp); j -=gap) {
				arr[j] = arr[j - gap];
			}
			arr[j] = temp;
 
			//increase i
			i++;
		}
 
		//reduce the gap by half
		gap = gap / 2;
	}
}
 
 
void print_array(int array[], int length)
{
	int index = 0;
 
	printf("The sorted array is: \n");
 
	for(index = 0 ; index < length ; index++)
	{
		printf("%d\n",array[index] );
	}
}
 
 
int main(void) {
		
	int length = 0;
	int array[100];
	int index = 0;
 
	printf("Enter the length of the array\n");
	scanf("%d", &length);
 
	printf("Enter the array elements of length %d = \n", length);
 
	for (index = 0; index < length; ++index)
	{
		scanf("%d", &array[index]);
	}
 
	shellSort(array, length);
 
	print_array(array, length);
 
 
 
	return 0;
}

Enter the length of the array
5
Enter the array elements of length 5 =
5
4
3
2
1
The sorted array is:
1
2
3
4
5

Time complexity is O (n^2)