Description

In this problem, you are asked to implement the quick sort algorithm. The quick sort algorithm is a divide and conquer algorithm that works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

• This is a partial judge problem. Input and output are handled by 14216.c. All you have to do is implement two functions pickPivot and rearrange.
• int* pickPivot(int* begin, int* end);
  This function should return a pointer to the pivot element. Notice that the pivot element should be in the array. How you choose the pivot will affect the performance of the quick sort algorithm. You should choose the pivot such that the array is divided into two sub-arrays of approximately equal size.
• int* rearrange(int* begin, int* end, int* pivot);
  This function should rearrange the elements in [begin, end) such that all elements less than to the pivot are to the left of the pivot, and all elements greater than the pivot are to the right of the pivot. The function should return a pointer to the pivot element after rearranging.

Input

The input consists of two lines. The first line contains an integer \(N\), the number of elements in the array. The second line contains \(N\) integers \(a_1, a_2, \cdots, a_N\), the elements of the array.

\(N\)
\(a_1 \quad a_2 \quad \cdots \quad a_N\)

Constraints

• \(1 \leq N \leq 10^5\)
• \(-10^9 \leq a_i \leq 10^9\)

Output

The output should contain one lines with \(N\) integers, the elements of the array after sorting. There should be a space after each integer.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14216.c

Partial Judge Header

14216.h

Tags

Discuss