//
//  quicksort3.c
//  
//
//  Created by Bibhas Ghoshal on 06/06/22.
//

#include <stdio.h>

// A utility function to swap two elements
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}


// Driver Code
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:\n");
    
    for(i=0; i<n; i++){
        printf("%d",*(data+i));
        printf("\n");
    }
    
    /* Call quicksort */
    
    quicksort(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");
}

/* The main function that implements QuickSort
 arr[] --> Array to be sorted,
 low --> Starting index,
 high --> Ending index */
quicksort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
         at right place */
        int pi = partition(arr, low, high);
        
        // Separately sort elements before
        // partition and after partition
        quicksort(arr, low, pi - 1);
        quicksort(arr, pi + 1, high);
    }
}

/* This function takes last element as pivot, places
 the pivot element at its correct position in sorted
 array, and places all smaller (smaller than pivot)
 to left of pivot and all greater elements to right
 of pivot */
int partition (int arr[], int low, int high)
{
    int pivot = arr[high]; // pivot
    int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far
    
    for (int j = low; j <= high - 1; j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++; // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]); //pivot is placed in the correct position
    return (i + 1);
}