#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