Quick Sort Problem Statement

Sort the given array of integers in ascending order using the quick sort algorithm. Quick sort is a divide-and-conquer algorithm where a pivot point is chosen to partition the array into two parts: numbers smaller than the pivot and numbers larger than it. The process is recursively repeated for both subarrays.

Input:

The first line contains an integer 'T' that represents the number of test cases.
The first line of each test case contains an integer 'N', the size of the array.
The second line contains 'N' space-separated integers denoting the elements of the array.

Output:

For each test case, the output is a single line of space-separated integers representing the sorted array.
Each test case's output should be printed on a new line.

Example:

Input:
array = [4, 2, 1, 5, 3] when using the rightmost element as a pivot.
Output:
{ 2, 1, 3, 4, 5 } after first partition.
{ 1, 2, 3, 4, 5 } after second partition for complete sorting.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10 ^ 3
• -10 ^ 9 <= ARR[i] <= 10 ^ 9

Note:

You are not required to print anything, as the printing function is already handled. Just implement the function for sorting the array.

Follow Up:

Consider solving it using the worst case NlogN time complexity.