## Question Name:Shell Sort

``````#include  <iostream>
using namespace std;

int shellSort(int arr[], int n)
{
for (int gap = n/2; gap > 0; gap /= 2)
{

for (int i = gap; i < n; i += 1)
{

int temp = arr[i];

int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];

arr[j] = temp;
}
for (int i=0; i<n; i++)
{ cout<<arr[i]<<" ";
} cout<<endl;

}
return 0;
}

int main()
{
int i;
int n ;
cin>>n;
int arr[n];

for(i=0;i<n;i++)
{
cin>>arr[i];
}

shellSort(arr, n); //don

return 0;
} ``````
• Problem Description
Implement Shell Sort for the given N inputs. You have to display the array after every pass.

Input Format:
The first line contains N, the number of inputs. The second line contains N space separated elements.

Output Format:
Print every iteration of the sort algorithm in separate lines as shown below.

Constraints:
1<=N<=50
1<=A[i]<=100
• Test Case 1
Input (stdin)5
3 8 1 4 2
Expected Output1 4 2 8 3
1 2 3 4 8
• Test Case 2
Input (stdin)8
12 3 8 1 7 5 4 2
Expected Output7 3 4 1 12 5 8 2
4 1 7 2 8 3 12 5
1 2 3 4 5 7 8 12