Using C$++,$Quick sort is one of the O$($n log n$)$ sorts we consider. it relies on the idea of recursively splitting a list into smaller sub$-$lists using a pivot, and sorting them.

The program should read in the number of values as an integer, allocate the necessary space, then read in all the values provided. Use a helper function, ReadNums$()$ to return the dynamic array, instead of inputting the values in main$().$

Create a function called PrintNums$()$ that prints out the array between a start and end index$($inclusive$).$ It should take as parameters the array as well as the starting and stopping indices in the array. It should print out the array between those index values with a space between each number, but no space at the end. Finish with a new line.

Complete a recursive function, QuickSort$().$ You may wish to use a helper function to compute the partition. for splitting the array. Always select the pivot as the right$-$most element in the sub$-$array.

Add code to the sort algorithm to count the number of swaps performed, to output the pivot and pivoted array before each recursive call, and to output the state of the sub$-$arrays after each recursive call.

Add code at the end of main$()$ that outputs "Swaps" followed by the number of swaps $($Ex: "Swaps: $2").$

Hint: Use a global variable to count the swaps.

Note: Take special care to look at the output of each test to better understand the quick sort algorithm.

Ex: When the input is:

$6321598$

the output is:

Unsorted:

$321598$

Pivot: $8$

$321589$

Pivot: $5$

$3215$

Pivot: $1$

$123$

Left Side:

Pivot: $3$

$23$

Left Side: $2$

Right Side:

Right Side: $23$

Left Side: $123$

Right Side:

Left Side: $1235$

Right Side: $9$

Sorted:

$123589$

Swaps: $2$