#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int n=12, A[12] = { 3, 1, 1, 5, 9, 5, 2, 4, 7, 6, 5, 0 };

void quickSort(int *a, int l, int r)
{
    srand(time(NULL));  //khoi tao tham so ham rand()
    int key = a[l + rand() % (r-l+1)];  //lay khoa la gia tri ngau nhien tu a[l] -> a[r]
    //int key = a[(l+r)/2];
    int i = l, j = r;
 
    while(i <= j)
    {
        while(a[i] <= key) i++;       // tim phan tu ben trai ma >=key
        while(a[j] >= key) j--;       // tim phan tu ben trai ma <=key
        if(i <= j)
        {
            if (i < j) { // swap fail
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
            i++;
            j--;
        }
    }
    //bay gio ta co 1 mang : a[l]....a[j]..a[i]...a[r]
    if (l < j) quickSort(a, l, j);   // lam lai voi mang a[l]....a[j]
    if (i < r) quickSort(a, i, r); // lam lai voi mang a[i]....a[r]
}

int main(void) {
	quickSort(A, 0, n-1);
	for (int i=0; i<n; i++) printf("%d ", A[i]);
	printf("\n");
}