Implement Shell Sort using C++ Programming Language

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:

Table of Contents

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.

Implement shell sort using C++



#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
88 15 34 99 55 44
Array after sorting is :15 34 44 55 88 99

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

Types of Sorting Algorithms:

Additional Reading

If you found this post useful, don’t forget to share this with your friends, and if you have any query feel free to comment it in the comment section.
Thank you 😊 Keep Learning !