IN C$++$

Part $1$: Implement Quicksort to Organize the Treasure

You must implement the $**$quicksort algorithm$**$ from scratch to sort the treasure. The

treasures will be represented as items with various values, and your goal is to sort them in

ascending order by their value.

Tasks:

$1.$ Implement the quicksort function that takes in a list of treasure values $($integers$)$ and

sorts them.

$2.$ Ensure your implementation includes the correct partitioning logic and recursive calls.

$3.$ Test your quicksort implementation by sorting treasure piles that range in size from small

$(10$ items$)$ to large $(1000+$ items$).$

$**$Helpful Hint$**$: Quicksort works best with smaller partitions and is one of the fastest

sorting algorithms in practice. However, remember that quicksort has a worst$-$case

behavior, so ensure you understand when and why that might occur.

Part $2$: Create Your Own Stack Data Structure

Since you$$re working in a magical keep with limited space, you must implement a $**$stack

data structure$**$ to help manage treasures temporarily during sorting. You will not be

allowed to use any existing stack libraries $($using an existing stack library will reduce

your grade by $50\%$ on this project$)!$

Tasks:

$1.$ Implement a basic stack class from scratch using arrays or a linked list. The stack should

have the following operations:

$-`$push$()`$: Adds an item to the top of the stack.

$-`$pop$()`$: Removes and returns the item from the top of the stack.

$-`$peek$()`$: Returns the top item without removing it$.$

$-`$isEmpty$()`$: Checks if the stack is empty.

$2.$ Use your stack in the quicksort implementation to manage recursive calls or as part of

the partitioning process.

$**$Helpful Hint$**$: A stack is useful for managing recursive processes or breaking down large

problems into smaller parts. You$$ll need to manage your stack operations efficiently to

ensure the enchanted treasure stays safe!

Part $3$: The Final Challenge $$ The Enchanted Vault

Once the treasures are sorted, you must unlock the vault by solving one final puzzle. This

puzzle will involve using both $**$quicksort$**$ and $**$stacks$**$ to rearrange magical keys in the

correct order. If the keys are sorted in the wrong order, the vault will remain locked forever.

Tasks:

$1.$ Implement a system where keys $($represented by a random sequence of numbers$)$ must

be sorted in descending order using your quicksort implementation.

$2.$ Use your stack to ensure that only a limited number of operations can be performed at

any given time $($e$.$g$.,$ no more than three keys can be moved simultaneously$).$

$3.$ Once the keys are sorted, the vault unlocks, and the treasure is revealed