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