# 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
```

Preparation

What's New

Top Interview Coding Problems/Challenges!