// Quick Sort example
// For input array
// 2 8 7 1 3 5 6 4
//
#include <stdio.h>
#define IPSIZE 8

// To enable debug messages uncomment #define
// #define DEBUG 1

#ifdef DEBUG
#  define D(x) x
#else
#  define D(x)
#endif

void quicksort(int arr[], int p, int r); 
int partition(int arr[], int p, int r); 
void swap(int i, int j); 

int arr[IPSIZE] = {2, 8, 7, 1, 3, 5, 6, 4}; 

int main()
{
	int i = 0;
    printf("Input array\n");
    for (i = 0; i <= IPSIZE - 1; i++) {
        printf("%d ", arr[i]);
    }   
    printf("\n\n");

    quicksort(arr, 0, IPSIZE - 1); 

    printf("Sorted output\n");
    for (i = 0; i <= IPSIZE - 1; i++) {
        printf("%d ", arr[i]);
    }   
    printf("\n");

    return 0;
}

void quicksort(int arr[], int p, int r)
{
    if (p < r) {
        int pivotIndx = partition(arr, p, r);

        quicksort(arr, p, pivotIndx - 1);
        quicksort(arr, pivotIndx + 1, r);
    }
}

int partition(int arr[], int p, int r)
{
    int pivot = arr[r];
    int i = p - 1;
    int j = 0;

    // Debug messages
    D(printf("\n############\n"));
    D(printf("Partition\n"));
    D(printf("p=%d, r=%d, pivot=%d\n", p, r, pivot));
    D(printf("Elements\n"));
    for (j = p; j <= r; j++) {
        D(printf("%d ", arr[j]));
    }
    D(printf("\n"));

    for (j = p; j <= r - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(i, j);
        }
    }

    swap(i + 1, r);

    D(printf("Elements after partition\n"));
    for (j = p; j <= r; j++) {
        D(printf("%d ", arr[j]));
    }
    D(printf("\n"));

    return (i + 1);
}

void swap(int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}