Time limit: 5000ms
Memory limit: 256mb

Description:
In this exercise, you are required to complete the function QuickSort which sorts some integers in ascending order. You can find the pseudocode in lecture notes. (ch6.pptx)

void QuickSort(int A[], int left, int right)
Sort A[left]...A[right] in ascending order.

The main function has been provided. It first asks the user to input the integers to A[] and then invokes the QuickSort function. Finally, it outputs these sorted integers.

You could declare some variables yourself in the QuickSort function. However, you are not allowed to use any addtional array to do the partition.

Sample Input 1:
10
2 1 4 10 3 5 7 8 9 6

Sample Output 1:
Input the number of integers:
Input these integers:
1 2 3 4 5 6 7 8 9 10

Sample Input 2:
5
1 2 1 2 1

Sample Output 2:
Input the number of integers:
Input these integers:
1 1 1 2 2

Code Template:

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

void PrintArray(int A[], int n)
{
    for(int i=0; i<n; i++)
        printf("%d ", A[i]);
    printf("\n");
}

void QuickSort(int A[], int left, int right)
{
    if(left<right)
    {
        int PivotValue = A[left];
        /*
            Fill in your code here.
            You can add some variables but no additional array.
        */
    }
}

int main()
{
    int n, *a;
    printf("Input the number of integers:\n");
    scanf("%d",&n);
    a = (int*)malloc(sizeof(int)*n);
    printf("Input these integers:\n");
    for(int i=0; i<n; i++)
        scanf("%d", &a[i]);
    QuickSort(a, 0, n-1);
    PrintArray(a, n);
    return 0;
}