Home » Data Structure

How shell sort works and how to sort an array by using shell sort?

In this article, we are going to learn the basics of shell sort and understand it’s working with the help of an example of c program.
Submitted by Manu Jemini, on January 15, 2018

Let’s understand the above example. The Elements are 14 19 27 10 35 33 42 44 and we start from the starting index.

We get 14 which is the first element; hence our array till now is sorted. We move ahead and take the second element 19 which is greater than the 14 so out array | 14 | 19 | is sorted.

Next element is 27 but our array is still sorted, | 14 | 19 | 27 |. Now comes the 10 which makes our array unsorted so we move on the first place. You can see the example above for better understanding.

Next is ‘35’ which is sorted and then comes ‘33’ which should be moved before the 35. Out array so far is | 10 | 14 | 19 | 27 | 33 | 35 | and it is sorted too.

Next is ‘42’ which make our array | 10 | 14 | 19 | 27 | 33 | 35 | 42 |, but it is still sorted.

Image source: https://www.tutorialspoint.com/data_structures_algorithms/images/shell_sort.jpg

Last element is 45, let’s add the 45 in the last and see if out array is sorted or not. | 10 | 14 | 19 | 27 | 33 | 35 | 42 | 45 |, well it is sorted. Good work.

Below is the code in C, have a look:

#include <stdio.h>
#define MAX 20
void shell(int arr[],int n,int incr)
{   int i,j,k;
	/*Shell sort*/
		while(incr>=1)
		{
			for(j=incr;j<n;j++)
			{	k=arr[j];
				for(i = j-incr; i >= 0 && k < arr[i]; i = i-incr)
					{arr[i+incr]=arr[i];}
				arr[i+incr]=k;
			}
			incr=incr-2; /*Decrease the increment*/
		}/*End of while*/
}

//main code
int main()
{	int arr[MAX], i,n,incr;
	printf("Enter the number of elements : ");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("Enter element %d : ",i+1);
		scanf("%d",&arr[i]);
	}
	printf("Unsorted list is :\n");
	for (i = 0; i < n; i++)
		{printf("%d ", arr[i]);}

	printf("\nEnter maximum increment (odd value) : ");
	scanf("%d",&incr);
	shell(arr,n,incr);
	printf("Sorted list is :\n");
	for (i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}/*End of main()*/

Output