#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