/**
 * Function to perform the quicksort partition - Theta(right-left)
 * @param a - array to be partitioned
 * @param left - left index
 * @param right - right index
 * @result p - index in a such that all elements a0..ap-1 <= ap and all elements ap+1..an-1 >= ap
 */
int partition(int a[], int left, int right) {
    int pivot = a[right];
    int i = left - 1;

    for (int j = left; j < right; j++) {
        if (a[j] < pivot) {
            i++;
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    int tmp = a[i + 1];
    a[i + 1] = a[right];
    a[right] = tmp;

    return i + 1;
}

/**
 * Function to sort a list using quicksort - complexity O(n^2) - avg Theta(nlogn)
 * @param a - list to be sorted
 * @param left - left index
 * @param right - right index
 * @result a permutation of list a such that (a0 <= a1 <=...<= an-1)
 */
void quickSortAux(int a[], int left, int right) {
    if (left < right) {
        int p = partition(a, left, right);
        quickSortAux(a, left, p - 1);
        quickSortAux(a, p + 1, right);
    }
}

/**
 * Function to sort a list using quicksort - complexity O(n^2) - avg Theta(nlogn)
 * @param a - list to be sorted
 * @param n - length of the list
 * @result a permutation of list a such that (a0 <= a1 <=...<= an-1)
 */
void quickSort(int a[], int n) {
    quickSortAux(a, 0, n - 1);
}