Program 4 - Quick Sort

	#include <stdio.h>
	int partition(int a[], int f, int l){
	int pivot, pindex, i, temp;
	//Last element is the pivot
	pivot = a[l];
	pindex = f;
	// Find correct position of pivot
	for(i = f; i < l; i++){
	// <l because there is no need to compare last element with itself
	if(a[i] <= pivot){
	//If element is less than pivot swap element at pindex and i
	// The equal to sign is to make this sort stable
	temp = a[i];
	a[i] = a[pindex];
	a[pindex] = temp;
	pindex++;
	}
	}
	//Put pivot in the correct position
	temp = a[l];
	a[l] = a[pindex];
	a[pindex] = temp;
	return pindex;
	}
	void quick_sort(int a[], int f, int l){
	int p;
	if(f < l){
	p = partition(a, f, l);
	quick_sort(a, f, p-1);
	quick_sort(a,p+1,l);
	}
	}
	int main(){
	int i;
	//Worst Case xD
	int a[] = {4,3,2,1,0,-1,-2,-3,-4};
	int n = sizeof(a)/ sizeof(a[0]);
	quick_sort(a,0, n-1);
	printf("The sorted array is: \n");
	for(i = 0; i < n; i++){
	printf("%d ", a[i]);
	}
	return 0;
	}