/*
 * Quick-sort program in C
 *
 * https://www.programiz.com/dsa/quick-sort
 */

#include <stdio.h>

	/*int data[] = { 8, 7, 2, 1, 0, 9, 6 }; */

	int data[] = { 8, 7, 6, 1, 0, 9, 2 };

/* Function to swap position of elements */
void swap(int *a, int *b) 
{
	int t = *a;
	*a = *b;
	*b = t;
}

/* Function to partition the array on the basis of pivot element */
int partition(int array[], int low, int high) 
{
	int pivot, i, j;
	
	/* Select the pivot element */
	pivot = array[high];
	i = low - 1;

	/* 
	 * Put the elements smaller than pivot on the left 
	 * and greater than pivot on the right of pivot
	 */
	for (j = low; j < high; j++) 
	{
		if (array[j] <= pivot) 
		{
			i++;
			swap(&array[i], &array[j]);
		}
	}

	swap(&array[i + 1], &array[high]);
	return (i + 1);
}

/* Quicksort is an algorithm based on divide and conquer approach */
void quickSort(int array[], int low, int high) 
{
	if (low < high) 
	{
		int pi;
		int i;
		
		printf("\n------------------------------------\n");
		
		for (i = low; i <= high; ++i) 
		{
			printf("%d ", array[i]);
		}
		printf("\n");
	
		/*
		 * Select pivot position and put all the elements smaller 
		 * than pivot on left and greater than pivot on right
		 */
		pi = partition(array, low, high);
		printf("Partition:\n");
				
		for (i = low; i <= high; ++i)
		{
			if (pi == i)
				printf("[%d] ", array[i]);
			else
				printf("%d ", array[i]);
		}

		if ((low < pi - 1) || (pi + 1 < high))
			printf("\nPivot index: %d, value: %d", pi,  array[pi]);
		else
		{
			printf("\nFinished\n------------------------------------\n");
			return;
		}

		/* Sort the elements on the left of pivot */
		if (low < pi - 1) 
		{
			quickSort(array, low, pi - 1);
		}

		/* Sort the elements on the right of pivot */
		if (pi + 1 < high) 
		{
			quickSort(array, pi + 1, high);
		}
	}
}

/* Function to print elements of an array */
void printArray(int array[], int size) 
{
	int i;
	for (i = 0; i < size; ++i) 
	{
		printf("%d ", array[i]);
	}
	printf("\n");
}

/* Entry point to program */
int main() 
{
	int size;
	
	size = sizeof(data) / sizeof(data[0]);
	
	printf("Unsorted array order:\n");
	printArray(data, size);
	
	quickSort(data, 0, size-1);
	
	printf("Sorted array in ascending order:\n");
	printArray(data, size);
}