Implement shell sort using C++ program

In this article, we are going to learn what is shell short in Data Structure and how to implement it using a C++ program?
Submitted by Shubham Singh Rajawat, on July 24, 2017

Shell sort is a generalization of insertion sort in which the exchange of far element is possible unlike insertion sort with the help of an element ‘gap’ and make the list gap-sorted we will keep decreasing gap until gap becomes 1 which means the last step will be a normal insertion sort.

Algorithm:

Step 1: Initialize the value of gap.

Step 2: Divide the list into smaller sub-lists of equal interval gap.

Step 3: Sort each sub-list using insertion sort.

Step 4: Repeat until the list is sorted.

Consider the given program:

#include<iostream>
using namespace std;

/*Method to sort the list/array*/
void shellSort(int sort[],int size)      
{
	for(int gap=size/2;gap>0;gap/=2)
	{
		for(int i=gap;i<size;i++)
		{
			int temp=sort[i];
			int j;
			for(j=i; j>=gap && sort[j-gap]>temp; j-=gap)
			{
				sort[j]=sort[j-gap];
			}
			sort[j]=temp;
		}
	}	
}

//main program
int main()
{
	int size;               

	cout<<"Enter the size of the array :";
	cin>>size;

	int sort[size];
	for(int i=0;i<size;i++)
	{
		cin>>sort[i];
	}

	shellSort(sort,size);

	cout<<"Array after sorting is :";
	for(int i=0;i<size;i++)
	{
		cout<<sort[i]<<" ";
	}

	cout<<endl;
	
	return 0;
}

Output

FIRST INPUT:
Enter the size of the array :6
87 15 34 99 56 44
Array after sorting is :15 34 44 56 87 99

SECOND INPUT :
Enter the size of the array :10
13 54 36 87 36 42 11 68 91 9
Array after sorting is :9 11 13 36 36 42 54 68 87 91