Shell Sort

The Shell Sort is a variation of insertion sort, but it is more effective. In insertion sort, the element is moving just one position at a time, which is time consuming and inefficient. But in shell sort, we can compare more elements at a time. It is an improvement over the insertion sort.

In shell sort, elements are sorted in multiple passes. At first, elements are divided in two parts and compare the same index position elements of both parts and interchange the values if the first part element is greater than the second part.

Shell sort example

These are the shell sorting technique.

Divide the elements in two parts, arrange them and sort the columns.

Now, combine both parts and we will get the following -

Again arrange the elements in three rows and sort them.

Again combine them.

Now, repeat the process of insertion sort.

Complexity of Shell sort

Suppose n is the number of element in an array.

Best Time Complexity - O(n*logn)
Worst Time Complexity - O(n)

Shell Sort Program in C

#include<stdio.h>
#include<conio.h>
#define MAX 20

int main() {

	int i, j, k, itr, temp, size, sort[MAX];

	printf("Enter the number of elements: \n");
	scanf("%d", &size);
	printf("\nEnter %d numbers\n", size);
	for (i = 0; i < size; i++)
	scanf("%d", &sort[i]);

	printf("\nYour Data   :");
	for (i = 0; i < size; i++) {
	printf("\t%d", sort[i]);
	}

	for (i = size / 2; i > 0; i = i / 2) {
	for (j = i; j < size; j++) {
	  for (k = j - i; k >= 0; k = k - i) {
		if (sort[k + i] >= sort[k])
		  break;
		else {
		  //Swapping Values 
		  temp = sort[k];
		  sort[k] = sort[k + i];
		  sort[k + i] = temp;
		}
	  }

	  printf("\nShell Sort Iteration [%d:%d] ", i, j);
	  for (itr = 0; itr < size; itr++) {
		printf("\t%d", sort[itr]);
	  }
	}

	}

	printf("\n\nSorted Data :");
	for (i = 0; i < size; i++) {
	printf("\t%d", sort[i]);
	}

	getch();
}

Enter the number of elements: 
10

Enter 10 numbers
11
22
33
21
31
41
44
52
25
43

Your Data   :	11	22	33	21	31	41	44	52	25	43
Shell Sort Iteration [5:5] 	11	22	33	21	31	41	44	52	25	43
Shell Sort Iteration [5:6] 	11	22	33	21	31	41	44	52	25	43
Shell Sort Iteration [5:7] 	11	22	33	21	31	41	44	52	25	43
Shell Sort Iteration [5:8] 	11	22	33	21	31	41	44	52	25	43
Shell Sort Iteration [5:9] 	11	22	33	21	31	41	44	52	25	43
Shell Sort Iteration [2:2] 	11	22	33	21	31	41	44	52	25	43
Shell Sort Iteration [2:3] 	11	21	33	22	31	41	44	52	25	43
Shell Sort Iteration [2:4] 	11	21	31	22	33	41	44	52	25	43
Shell Sort Iteration [2:5] 	11	21	31	22	33	41	44	52	25	43
Shell Sort Iteration [2:6] 	11	21	31	22	33	41	44	52	25	43
Shell Sort Iteration [2:7] 	11	21	31	22	33	41	44	52	25	43
Shell Sort Iteration [2:8] 	11	21	25	22	31	41	33	52	44	43
Shell Sort Iteration [2:9] 	11	21	25	22	31	41	33	43	44	52
Shell Sort Iteration [1:1] 	11	21	25	22	31	41	33	43	44	52
Shell Sort Iteration [1:2] 	11	21	25	22	31	41	33	43	44	52
Shell Sort Iteration [1:3] 	11	21	22	25	31	41	33	43	44	52
Shell Sort Iteration [1:4] 	11	21	22	25	31	41	33	43	44	52
Shell Sort Iteration [1:5] 	11	21	22	25	31	41	33	43	44	52
Shell Sort Iteration [1:6] 	11	21	22	25	31	33	41	43	44	52
Shell Sort Iteration [1:7] 	11	21	22	25	31	33	41	43	44	52
Shell Sort Iteration [1:8] 	11	21	22	25	31	33	41	43	44	52
Shell Sort Iteration [1:9] 	11	21	22	25	31	33	41	43	44	52

Sorted Data :	11	21	22	25	31	33	41	43	44	52