#include <stdio.h>

void interchange(int a[], int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

int partition(int a[], int p, int q) {
    int v = a[p];
    int i = p, j = q + 1;
    
    do {
        do {
            i = i + 1;
        } while (a[i] < v && i <= q);
        
        do {
            j = j - 1;
        } while (a[j] > v && j >= p);
        
        if (i < j) {
            interchange(a, i, j);
        }
    } while (i < j);

    // Swap the pivot with the element at j
    interchange(a, p, j);
    
    return j;
}

void quickSort(int a[], int p, int q) {
    if (p < q) {
        int j = partition(a, p, q);
        quickSort(a, p, j - 1);
        quickSort(a, j + 1, q);
    }
}

int main() {
    int n;
    printf("Enter Size: ");
    scanf("%d", &n);
    
    int a[n];
    
    printf("Enter elements: \n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    
    quickSort(a, 0, n - 1);
    
    printf("Sorted Array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    
    return 0;
}