#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");
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHRpbWUuaD4KCmludCBuPTEyLCBBWzEyXSA9IHsgMywgMSwgMSwgNSwgOSwgNSwgMiwgNCwgNywgNiwgNSwgMCB9OwoKdm9pZCBxdWlja1NvcnQoaW50ICphLCBpbnQgbCwgaW50IHIpCnsKICAgIHNyYW5kKHRpbWUoTlVMTCkpOyAgLy9raG9pIHRhbyB0aGFtIHNvIGhhbSByYW5kKCkKICAgIGludCBrZXkgPSBhW2wgKyByYW5kKCkgJSAoci1sKzEpXTsgIC8vbGF5IGtob2EgbGEgZ2lhIHRyaSBuZ2F1IG5oaWVuIHR1IGFbbF0gLT4gYVtyXQogICAgLy9pbnQga2V5ID0gYVsobCtyKS8yXTsKICAgIGludCBpID0gbCwgaiA9IHI7CiAKICAgIHdoaWxlKGkgPD0gaikKICAgIHsKICAgICAgICB3aGlsZShhW2ldIDw9IGtleSkgaSsrOyAgICAgICAvLyB0aW0gcGhhbiB0dSBiZW4gdHJhaSBtYSA+PWtleQogICAgICAgIHdoaWxlKGFbal0gPj0ga2V5KSBqLS07ICAgICAgIC8vIHRpbSBwaGFuIHR1IGJlbiB0cmFpIG1hIDw9a2V5CiAgICAgICAgaWYoaSA8PSBqKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGkgPCBqKSB7IC8vIHN3YXAgZmFpbAogICAgICAgICAgICAgICAgaW50IHQgPSBhW2ldOwogICAgICAgICAgICAgICAgYVtpXSA9IGFbal07CiAgICAgICAgICAgICAgICBhW2pdID0gdDsKICAgICAgICAgICAgfQogICAgICAgICAgICBpKys7CiAgICAgICAgICAgIGotLTsKICAgICAgICB9CiAgICB9CiAgICAvL2JheSBnaW8gdGEgY28gMSBtYW5nIDogYVtsXS4uLi5hW2pdLi5hW2ldLi4uYVtyXQogICAgaWYgKGwgPCBqKSBxdWlja1NvcnQoYSwgbCwgaik7ICAgLy8gbGFtIGxhaSB2b2kgbWFuZyBhW2xdLi4uLmFbal0KICAgIGlmIChpIDwgcikgcXVpY2tTb3J0KGEsIGksIHIpOyAvLyBsYW0gbGFpIHZvaSBtYW5nIGFbaV0uLi4uYVtyXQp9CgppbnQgbWFpbih2b2lkKSB7CglxdWlja1NvcnQoQSwgMCwgbi0xKTsKCWZvciAoaW50IGk9MDsgaTxuOyBpKyspIHByaW50ZigiJWQgIiwgQVtpXSk7CglwcmludGYoIlxuIik7Cn0=