// To implement quick sort

#include <stdio.h>
#include <stdlib.h>
#define MAX 20

void display(int a[], int n){
    int i;
    printf("\n Elements in array: ");
    for( i=0; i<n; i++)
        printf(" %d ", a[i]);
}

void sort(int ary[], int left,int right){
    int l = left, r = right, tmp;
    int p = left; //p is pivot, start from left

    if( left>=right)
        return;

    while( l<r ){
        while( ary[p] <= ary[r] && p!=r)
            r--;
        if( p == r)
            break;
        // swap
        if( ary[p] > ary[r] ){
            tmp = ary[r];
            ary[r] = ary[p];
            ary[p] = tmp;
            p = r;
        }
        while( ary[p] >= ary[l] && p!=l)
            l++;
        if(p==l)
            break;
         // swap
        if( ary[p] < ary[l] ){
            tmp = ary[l];
            ary[l] = ary[p];
            ary[p] = tmp;
            p = l;
        }
    }

    sort(ary, left, p-1);
    sort(ary, p+1, right);
}

int main(){
    int a[20];
    int n, i;
    
    printf("\n Enter total number of elements in array (max. %d): ", MAX);
    scanf("%d", &n);
    
    if( n < 0)
        printf("UNDERFLOW \n");
    else if( n > MAX)
        printf("OVERFLOW \n");
    else{
        // input elements one by one
        printf("\n Enter item(s) one by one\n");
        for( i=0; i<n; i++){
            printf(" Enter item no %d : ",i);
            scanf("%d", &a[i]);
        }
        
        printf("\n Before Sorting");
        display(a,n);
        sort( a, 0, n-1);
        printf("\n After Sorting");
        display(a,n);
        printf("\n ");
    }
        
    system("pause");
    return 0;
}