#include <iostream>
#include <ctime>
using namespace std;

int Partition(int A[], int start, int end) {
    int key = A[end];
    int pi = start;
    for (int i = start; i < end; i++) {
        if (A[i] < key) {
            swap(A[i], A[pi]);
            pi++;
        }
    }
    swap(A[pi], A[end]);
    return pi;
}

void Quick_sort(int A[], int start, int end) {
    if (start < end) {
        int pi = Partition(A, start, end);
        Quick_sort(A, start, pi - 1);
        Quick_sort(A, pi + 1, end);
    }
}



int main() {
    int n, i;
    cout << "Enter the size of the array: ";
    cin >> n;
    int A[n];
    cout << "Enter the elements: ";
    for (i = 0; i < n; i++) {
        cin >> A[i];
    }
    clock_t start = clock();
    Quick_sort(A, 0, n - 1);
    clock_t end = clock();
    cout << "Sorted array: ";
    for (i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
     double time_taken = double(end - start) / CLOCKS_PER_SEC * 1000;
    cout <<endl<< "Time taken to sort the array: " << time_taken << " ms" << endl;
    return 0;
}