#include<iostream>
 
#include<time.h>
using namespace std;
 
int partition (int *a, int s, int e)
{
    int i=s;
    int j=e-1;
    int pivot = a[e],temp;
    while (i<=j)
    {
          if  (a[i] < pivot)
          {
              i++;
              continue;
          }
          if  (a[j] > pivot)
          {
              j--;
              continue;
          }
 
          temp = a[i];
          a[i] = a[j];
          a[j] = temp;
          i++;
          j--;
    }
 
    temp = a[i];
    a[i] = a[e];
    a[e] = temp;
    return i;
}
 
 
 
 
void qsort (int *a, int s, int e)
{
     if  (s>=e)
     {
         return;
     }
     int i = partition (a,s,e);
     qsort(a,s,i-1);
     qsort(a,i,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]<<" ";
    }
    cout<<endl;
    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+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgcGFydGl0aW9uIChpbnQgKmEsIGludCBzLCBpbnQgZSkKewogICAgaW50IGk9czsKICAgIGludCBqPWUtMTsKICAgIGludCBwaXZvdCA9IGFbZV0sdGVtcDsKICAgIHdoaWxlIChpPD1qKQogICAgewogICAgICAgICAgaWYgIChhW2ldIDwgcGl2b3QpCiAgICAgICAgICB7CiAgICAgICAgICAgICAgaSsrOwogICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgfQogICAgICAgICAgaWYgIChhW2pdID4gcGl2b3QpCiAgICAgICAgICB7CiAgICAgICAgICAgICAgai0tOwogICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgfQogICAgICAgICAgCiAgICAgICAgICB0ZW1wID0gYVtpXTsKICAgICAgICAgIGFbaV0gPSBhW2pdOwogICAgICAgICAgYVtqXSA9IHRlbXA7CiAgICAgICAgICBpKys7CiAgICAgICAgICBqLS07CiAgICB9CiAgICAKICAgIHRlbXAgPSBhW2ldOwogICAgYVtpXSA9IGFbZV07CiAgICBhW2VdID0gdGVtcDsKICAgIHJldHVybiBpOwp9CgoKCgp2b2lkIHFzb3J0IChpbnQgKmEsIGludCBzLCBpbnQgZSkKewogICAgIGlmICAocz49ZSkKICAgICB7CiAgICAgICAgIHJldHVybjsKICAgICB9CiAgICAgaW50IGkgPSBwYXJ0aXRpb24gKGEscyxlKTsKICAgICBxc29ydChhLHMsaS0xKTsKICAgICBxc29ydChhLGksZSk7Cn0KCgppbnQgbWFpbigpCnsKICAgIGludCBhWzEwMF07CiAgICBpbnQgaSxqOwogICAgaW50IG4gPSBzaXplb2YoYSkvc2l6ZW9mKGFbMF0pOwogICAgc3JhbmQodGltZShOVUxMKSk7CiAgICBmb3IgKGo9MDtqPG47aisrKQogICAgewogICAgICAgIGFbal0gPSByYW5kKCklNDA7CiAgICAgICAgY291dDw8YVtqXTw8IiAiOwogICAgfQogICAgY291dDw8ZW5kbDsKICAgIGNsb2NrX3Qgc3RhcnQgPSBjbG9jaygpOwogICAgcXNvcnQoYSwwLG4tMSk7CiAgICAKICAgIAogICAgZm9yIChpPTA7aTxuO2krKykKICAgIHsKICAgICAgICBjb3V0PDxhW2ldPDwiICAiOwogICAgfQogICAgY291dDw8IlxuVGltZSBlbGFwc2VkOiAiPDwoKGRvdWJsZSljbG9jaygpIC0gc3RhcnQpIC8gQ0xPQ0tTX1BFUl9TRUM8PGVuZGw7Cn0K