#include<iostream>
 
#include<time.h>
using namespace std;
 
void partition (int *a, int s, int e, int &start, int &end)
{
     start=s-1; 
     int mid=s;
     end=e;
 
     int pivot=a[e],temp,i;
 
     while (mid < end)
     {
           if  (a[mid] < pivot)
           {
               temp = a[start+1];
               a[start+1] = a[mid];
               a[mid] = temp;
               start++;
               mid++;     
           }
           else if (a[mid] == pivot)
           {
                mid++;
           }
           else
           {
               temp = a[end-1];
               a[end-1] = a[mid];
               a[mid] = temp;
               end--;
           }
     }
     temp = a[mid];
     a[mid] = a[e];
     a[e] = temp;
     cout<<start<<" "<<end<<"\n";
}
 
void Qsort(int *a, int s, int e)
{
     if (s>=e)
        return;
     int start,end;
     partition(a,s,e,start,end);
     Qsort(a,s,start);
     Qsort(a,end+1,e);
}
 
int main()
{
    int a[100];
    int i,j;
    int n = sizeof(a)/sizeof(a[0]);
    srand(time(NULL));
    for (j=0;j<n;j++)
    {
        a[j] = rand()%40;
        cout<<a[j]<<" ";
    }
    clock_t start = clock();
    Qsort(a,0,n-1);
 
    for (i=0;i<n;i++)
    {
        cout<<a[i]<<"  ";
    }
    cout<<"\nTime elapsed: "<<((double)clock() - start) / CLOCKS_PER_SEC<<endl;
 
}
 

I2luY2x1ZGU8aW9zdHJlYW0+CgojaW5jbHVkZTx0aW1lLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2b2lkIHBhcnRpdGlvbiAoaW50ICphLCBpbnQgcywgaW50IGUsIGludCAmc3RhcnQsIGludCAmZW5kKQp7CiAgICAgc3RhcnQ9cy0xOyAKICAgICBpbnQgbWlkPXM7CiAgICAgZW5kPWU7CiAgICAgCiAgICAgaW50IHBpdm90PWFbZV0sdGVtcCxpOwogICAgIAogICAgIHdoaWxlIChtaWQgPCBlbmQpCiAgICAgewogICAgICAgICAgIGlmICAoYVttaWRdIDwgcGl2b3QpCiAgICAgICAgICAgewogICAgICAgICAgICAgICB0ZW1wID0gYVtzdGFydCsxXTsKICAgICAgICAgICAgICAgYVtzdGFydCsxXSA9IGFbbWlkXTsKICAgICAgICAgICAgICAgYVttaWRdID0gdGVtcDsKICAgICAgICAgICAgICAgc3RhcnQrKzsKICAgICAgICAgICAgICAgbWlkKys7ICAgICAKICAgICAgICAgICB9CiAgICAgICAgICAgZWxzZSBpZiAoYVttaWRdID09IHBpdm90KQogICAgICAgICAgIHsKICAgICAgICAgICAgICAgIG1pZCsrOwogICAgICAgICAgIH0KICAgICAgICAgICBlbHNlCiAgICAgICAgICAgewogICAgICAgICAgICAgICB0ZW1wID0gYVtlbmQtMV07CiAgICAgICAgICAgICAgIGFbZW5kLTFdID0gYVttaWRdOwogICAgICAgICAgICAgICBhW21pZF0gPSB0ZW1wOwogICAgICAgICAgICAgICBlbmQtLTsKICAgICAgICAgICB9CiAgICAgfQogICAgIHRlbXAgPSBhW21pZF07CiAgICAgYVttaWRdID0gYVtlXTsKICAgICBhW2VdID0gdGVtcDsKICAgICBjb3V0PDxzdGFydDw8IiAiPDxlbmQ8PCJcbiI7Cn0KCnZvaWQgUXNvcnQoaW50ICphLCBpbnQgcywgaW50IGUpCnsKICAgICBpZiAocz49ZSkKICAgICAgICByZXR1cm47CiAgICAgaW50IHN0YXJ0LGVuZDsKICAgICBwYXJ0aXRpb24oYSxzLGUsc3RhcnQsZW5kKTsKICAgICBRc29ydChhLHMsc3RhcnQpOwogICAgIFFzb3J0KGEsZW5kKzEsZSk7Cn0KCmludCBtYWluKCkKewogICAgaW50IGFbMTAwXTsKICAgIGludCBpLGo7CiAgICBpbnQgbiA9IHNpemVvZihhKS9zaXplb2YoYVswXSk7CiAgICBzcmFuZCh0aW1lKE5VTEwpKTsKICAgIGZvciAoaj0wO2o8bjtqKyspCiAgICB7CiAgICAgICAgYVtqXSA9IHJhbmQoKSU0MDsKICAgICAgICBjb3V0PDxhW2pdPDwiICI7CiAgICB9CiAgICBjbG9ja190IHN0YXJ0ID0gY2xvY2soKTsKICAgIFFzb3J0KGEsMCxuLTEpOwogICAgCiAgICBmb3IgKGk9MDtpPG47aSsrKQogICAgewogICAgICAgIGNvdXQ8PGFbaV08PCIgICI7CiAgICB9CiAgICBjb3V0PDwiXG5UaW1lIGVsYXBzZWQ6ICI8PCgoZG91YmxlKWNsb2NrKCkgLSBzdGFydCkgLyBDTE9DS1NfUEVSX1NFQzw8ZW5kbDsKCn0K