$4\mathrm{.}15$ LAB: Quick sort

Quick sort is one of the $O(nlogn)$ 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: You may 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:

$6,3,2,1,5,9,8$

the output is:

Unsorted:

Pivot: $8$

Pivot: $5$

Pivot: $1$

$1\}22$

Left Side:

Pivot: $3$

$2\}$

Left Side: $2$

Right Side:

Right Side: $23$

Left Side: $123$

Right Side:

Left Side: $\}12$

Right Side: $9$

Sorted:

Swaps: $2$

$573646\mathrm{.}4034340\mathrm{.}93$zay$7$

Latest submission $-2$:$45$ PM CDT on $09/28/24$

Total score: $\frac{0}{100}$

Only show failing tests

Download this submission

$1$:Compare output

Output differs. See highlights below.

Input

$6$

Unsorted:

$3,2,1,5,9,8$

Pivot: $8$

$3,2,1,5,9,8$

Pivot: $5$

$32215$

Pivot: $1$

$321$

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:

$1,2,3,5,8,9$

Swaps: $12$

Unsorted:

$3,2,1,5,9,8$

Pivot: $8$

$3,2,1,5,8,9$

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:

$1235859$

Swaps: $2$

Compare output

Output differs: See highlights