#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stack>
#include <vector>
using namespace std;
// Exchange two elements in an array
void exchange(int arr[], int i, int j) {
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
// Partition an array and return the partition point
int partition(int arr[], int begin, int end)
{
int pivot = arr[end];
int i = begin-1;
int j;
for(j=begin;j<end;j++)
{
if(arr[j]<=pivot)
{
i=i+1;
exchange(arr,i,j);
}
}
exchange(arr,i+1,end);
return i+1;
}
void quickSort(int arr[], int begin, int end) {
int q=partition(arr,begin,end);
if(begin<end)
{
quickSort(arr,begin,q-1);
quickSort(arr,q+1,end);
}
}
void testQuickSort() {
srand (time(NULL));
int a[10], i = 0;;
printf("Before sorting, array a is\n");
for (i = 0; i < sizeof(a)/sizeof(int); ++i) {
a[i] = rand()%100;
printf("%d ", a[i]);
}
quickSort(a, 0, sizeof(a)/sizeof(int) - 1);
printf("\nAfter sorting, array a is\n");
for (i = 0; i < sizeof(a)/sizeof(int); ++i)
printf("%d ", a[i]);
printf("\n");
}
int main() {
testQuickSort();
return 0;
}