#include <stdio.h>
#include <time.h>
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int partition(int a[], int l, int h)
{
int x = a[h];
int i = (l - 1);
for (int j = l; j <= h - 1; j++) {
if (a[j] <= x) {
i++;
swap(&a[i], &a[j]);
}
}
swap(&a[i + 1], &a[h]);
return (i + 1);
}
void quickSort(int a[], int l, int h)
{
int stack[h - l + 1];
int top = -1;
stack[++top] = l;
stack[++top] = h;
while (top >= 0) {
h = stack[top--];
l = stack[top--];
int p = partition(a, l, h);
if (p - 1 > l) {
stack[++top] = l;
stack[++top] = p - 1;
}
if (p + 1 < h) {
stack[++top] = p + 1;
stack[++top] = h;
}
}
}
int main()
{
clock_t start, end;
double cpu_time_used;
int n,i,a[100000];
for(i=0;i<n;i++)
quickSort(a, 0, n - 1);
for (i = 0; i < n; ++i)
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("The time of execution is: %lf", cpu_time_used
); return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+IAojaW5jbHVkZSA8dGltZS5oPgoKdm9pZCBzd2FwKGludCogYSwgaW50KiBiKSAKeyAKICAgIGludCB0ID0gKmE7IAogICAgKmEgPSAqYjsgCiAgICAqYiA9IHQ7IAp9IAogIAppbnQgcGFydGl0aW9uKGludCBhW10sIGludCBsLCBpbnQgaCkgCnsgCiAgICBpbnQgeCA9IGFbaF07IAogICAgaW50IGkgPSAobCAtIDEpOyAKICAKICAgIGZvciAoaW50IGogPSBsOyBqIDw9IGggLSAxOyBqKyspIHsgCiAgICAgICAgaWYgKGFbal0gPD0geCkgeyAKICAgICAgICAgICAgaSsrOyAKICAgICAgICAgICAgc3dhcCgmYVtpXSwgJmFbal0pOyAKICAgICAgICB9IAogICAgfSAKICAgIHN3YXAoJmFbaSArIDFdLCAmYVtoXSk7IAogICAgcmV0dXJuIChpICsgMSk7IAp9IAogIAp2b2lkIHF1aWNrU29ydChpbnQgYVtdLCBpbnQgbCwgaW50IGgpIAp7IAogICBpbnQgc3RhY2tbaCAtIGwgKyAxXTsgCiAgCiAgICBpbnQgdG9wID0gLTE7IAogIAogICAgc3RhY2tbKyt0b3BdID0gbDsgCiAgICBzdGFja1srK3RvcF0gPSBoOyAKICAKICAgIHdoaWxlICh0b3AgPj0gMCkgeyAKICAgICAgICBoID0gc3RhY2tbdG9wLS1dOyAKICAgICAgICBsID0gc3RhY2tbdG9wLS1dOyAKCiAgICAgICAgaW50IHAgPSBwYXJ0aXRpb24oYSwgbCwgaCk7IAoKICAgICAgICBpZiAocCAtIDEgPiBsKSB7IAogICAgICAgICAgICBzdGFja1srK3RvcF0gPSBsOyAKICAgICAgICAgICAgc3RhY2tbKyt0b3BdID0gcCAtIDE7IAogICAgICAgIH0gCiAgCiAgICAgICAgaWYgKHAgKyAxIDwgaCkgeyAKICAgICAgICAgICAgc3RhY2tbKyt0b3BdID0gcCArIDE7IAogICAgICAgICAgICBzdGFja1srK3RvcF0gPSBoOyAKICAgICAgICB9IAogICAgfSAKfSAKIAppbnQgbWFpbigpIAp7IAogICAgICAgY2xvY2tfdCBzdGFydCwgZW5kOwogICAgIGRvdWJsZSBjcHVfdGltZV91c2VkOwogICAgIAogICAgIHN0YXJ0ID0gY2xvY2soKTsKCiAgICAgaW50IG4saSxhWzEwMDAwMF07CiAgICBzY2FuZigiJWQiLCZuKTsKICAgICBmb3IoaT0wO2k8bjtpKyspCiAgICAgc2NhbmYoIiVkIiwmYVtpXSk7CiAgICBxdWlja1NvcnQoYSwgMCwgbiAtIDEpOyAKICAgICBmb3IgKGkgPSAwOyBpIDwgbjsgKytpKSAKICAgICAgICBwcmludGYoIiVkICAiLCBhW2ldKTsgCiAgICAgIGVuZCA9IGNsb2NrKCk7CiAgICAgY3B1X3RpbWVfdXNlZCA9ICgoZG91YmxlKSAoZW5kIC0gc3RhcnQpKSAvIENMT0NLU19QRVJfU0VDOwogICAgICAgcHJpbnRmKCJUaGUgdGltZSBvZiBleGVjdXRpb24gaXM6ICVsZiIsIGNwdV90aW1lX3VzZWQpOwogICAgcmV0dXJuIDA7IAp9IA==