#include<iostream>
#define max 100 
using namespace std;

class A {
    int arr[max];
    int n;
    public:
    
    void getdata()
    {
        cout<<"Enter The  Size Of Array";
        cin>>n;
        cout<<"Enter The Elements In Array";
        
        for (int i = 0; i < n; i++)
        cin>>arr[i];
        quick(0,n-1);
    }
    void swap(int* a, int* b)  
    {  
        int t = *a;  
        *a = *b;  
        *b = t;  
    }
    int sort(int arr[], int n) 
{  
    if (n == 1 || n == 0) 
        return 1; 
   
    if (arr[n - 1] < arr[n - 2]) 
        return 0; 
 
    return sort(arr, n - 1); 
} 
 
    int divide(int i,int j)
    {
        int pivot=arr[i];
        int z=i,a=1;
        while(i<=j)
        {
            if(pivot>=arr[i])
                i++;
            if(pivot<=arr[i])
               j++;
            if(i<j)
                swap(&arr[i], &arr[j]); 
        }
        swap(&arr[z], &arr[j]); 
        cout<<"\nPass"<<a++<<" :\t ";
      	for (int k = 0; k < n; k++)
          		cout<<" "<<arr[k]<<" ";
          		
          	
 
        return (j+1);
       
    }
    void quick(int i,int j)
    {
        if (i < j)  
        {  
            int mid = divide( i, j);  
            
            quick( i, mid - 1);  
            quick( mid + 1, j);  
        }      
    }
    void print()
    {
        int i; 
    	cout<<"\n Sorted Array :\t ";
		for (i = 0; i < n; i++) 
			cout << arr[i] << " "; 
 
		cout << endl; 
 
    }
};
int main()
{   
    A x;
    x.getdata();
    x.print();
    return 0;
}