Time limit: 5000ms
Memory limit: 256mb

Description:
In this exercise, you are required to complete the function QuickSortParity which move all the even integers at the beginning of the array followed by all the odd integers and these integers are in ascending order.

void QuickSortParity(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 QuickSortParity function. Finally, it outputs these sorted integers.

You could declare some variables yourself in the QuickSortParity 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:
2 4 6 8 10 1 3 5 7 9 

Sample Input 2:
5
1 2 1 2 1

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

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 QuickSortParity(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]);
    QuickSortParity(a, 0, n-1);
    PrintArray(a, n);
    return 0;
}