#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

void swap(double *p, double *q);
void partition(double* a, int n, int *m);
void quickSort(double* a, int n);

int main() {
    int n, idx, i;
    double *a = NULL;
    while (true) {
        printf("n:\n");
        if (scanf("%d", &n) < 1 || n <= 0)
            break;

        delete[] a;
        a = new double[n];

        for (i = 0; i < n; ++i) {
            a[i] = (double)(rand() % 100);
        }

        for (i = 0; i < n; ++i) {
            printf("%5.1lf", a[i]);
            if ((i+1) % 10 == 0)
                printf("\n");
        }
        printf("\n====\n");

        quickSort(a, n);

        printf("Sorted:\n");

        for (i = 0; i < n; ++i) {
            printf("%5.1lf", a[i]);
            if ((i+1) % 10 == 0)
                printf("\n");
        }
        printf("\n====\n");
    }

    delete[] a;
    return 0;
}

void quickSort(double* a, int n) {
    if (n <= 1) {
        return;
    } else if (n == 2) {
        if (a[0] > a[1])
            swap(&(a[0]), &(a[1]));
        return;
    }

    int beg = 0;
    int k = n;
    while (k > 1) {
        int m = k / 2;
        partition(a+beg, k, &m);

        int left = m;
        int right = k - left - 1;
        if (left <= right) {
            // Recursive call for the left part of sub-array
            quickSort(a+beg, left);
            beg += left + 1;
            k -= left + 1;
        } else {
            // Recursive call for the right part of sub-array
            quickSort(a+beg+m+1, right);
            k -= right + 1;
        }
    }
}

void partition(double* a, int n, int *m) {
    if (*m != 0)
        swap(&(a[0]), &(a[*m]));
    double x = a[0];
    int i = 0;
    int j = n;
    while (j-i > 1) {
        bool changed = false;
        if (a[i+1] <= x) {
            ++i; changed = true;
        }
        if (j-1 >= i && a[j-1] >= x) {
            --j; changed = true;
        }
        if (!changed) {
            assert(
                j-i > 1 &&
                a[i+1] > x && a[j-1] < x
            );
            ++i; --j;
            swap(&(a[i]), &(a[j]));
        }
    }

    if (i > 0)
        swap(&(a[0]), &(a[i]));
    *m = i;
}

void swap(double *p, double *q) {
    double tmp = *p;
    *p = *q; *q = tmp;
}