//
//  quicksort.c
//  
//
//  Created by Bibhas Ghoshal on 04/06/22.
//

#include <stdio.h>
int main()
{
    int data[100],i,j,n,temp;
    
    /* Read N */
    
    printf("Give n:");
    scanf("%d",&n);
    printf("\n n = %d \n",n);
    
    for(i=0; i<n; i++)
        scanf("%d",data+i);
    
    printf("\n numbers read are:");
    
    for(i=0; i<n; i++){
        printf("%d",*(data+i));
        printf("\n");
    }
    
    /* Call quicksort */
    
    qsort(data,0,n-1);
    
    /* print result */
    printf("\n Sorted numbers are:");
    
    for(i=0; i<n; i++){
        printf("\n %d",data[i]);}
    //printf("\n");}
    printf("\n");
}

int qsort(a,i,j)
int a[],i,j;
{
    int k;
    
    if( i>=j) return 0;
    partition(a,i,j,&k);
    qsort(a,i,k-1);
    qsort(a,k+1,j);
    
}

partition(a,i,j,l)
int a[],i,j,*l;
{
    int b[50],p,q,m,n,count,temp;
    p=a[i];
    m = i+1;
    n = j;
    count = 0;
    
    for(q=i+1;q<=j;q++)
        if(a[q]>=p){
            b[m++] = a[q];
            count++;
        }
        else b[n--] = a[q];
            
    b[i] = b[i+count];
    b[i+count] = p;
    *l = i + count;
            
 for(q=i;q<=j;q++)
     a[q]= b[q];
     
}