Implementing the Strategy Pattern in TypeScript

The Strategy pattern is a behavioral design pattern that allows an algorithm to vary at runtime. It defines a family of algorithms, encapsulates each one, and makes them interchangeable. This challenge will guide you in implementing the Strategy pattern using TypeScript's type system to ensure type safety and clarity.

Problem Description

You are tasked with creating a system that can perform different sorting algorithms based on a user's selection. The system should be flexible enough to easily add new sorting algorithms without modifying the core sorting logic. You need to implement the Strategy pattern to achieve this, utilizing TypeScript's type system to define the strategy interface and ensure that all strategies adhere to the expected contract.

Specifically, you need to:

1. Define a SortingStrategy interface: This interface should define a single method, sort(data: number[]): number[], which accepts an array of numbers and returns a sorted array of numbers.
2. Implement three concrete sorting strategies:
   • BubbleSort: Implements the bubble sort algorithm.
   • QuickSort: Implements the quicksort algorithm.
   • MergeSort: Implements the merge sort algorithm.
3. Create a Sorter class: This class will hold a SortingStrategy instance and delegate the sorting operation to it. The Sorter class should have a constructor that accepts a SortingStrategy and a sort(data: number[]): number[] method that uses the injected strategy to sort the data.
4. Demonstrate the usage: Create instances of the concrete sorting strategies and the Sorter class, and demonstrate how to sort an array of numbers using each strategy.

Expected Behavior:

The Sorter class should correctly delegate the sorting operation to the currently injected SortingStrategy. The output should be a sorted array of numbers, regardless of which sorting algorithm is used. The code should be type-safe, leveraging TypeScript's type system to prevent errors.

Edge Cases to Consider:

• Empty input array: The sorting algorithms should handle empty arrays gracefully (returning an empty array).
• Array with a single element: The sorting algorithms should handle arrays with a single element correctly (returning the same array).
• Array with duplicate elements: The sorting algorithms should handle arrays with duplicate elements correctly.
• Negative numbers: The sorting algorithms should handle negative numbers correctly.

Examples

Example 1:

Input: data = [5, 2, 8, 1, 9, 4], strategy = BubbleSort
Output: [1, 2, 4, 5, 8, 9]
Explanation: The BubbleSort strategy sorts the input array in ascending order.

Example 2:

Input: data = [10, 7, 8, 9, 1, 5], strategy = QuickSort
Output: [1, 5, 7, 8, 9, 10]
Explanation: The QuickSort strategy sorts the input array in ascending order.

Example 3:

Input: data = [], strategy = MergeSort
Output: []
Explanation: The MergeSort strategy handles an empty array by returning an empty array.

Constraints

• The sorting algorithms must be implemented in-place or create a new array to avoid modifying the original input array.
• The sort method in the SortingStrategy interface must return a new sorted array.
• The code must be written in TypeScript and adhere to good coding practices.
• The time complexity of the sorting algorithms is not a primary concern for this challenge, but reasonable implementations are expected.

Notes

• Consider using TypeScript generics to make the SortingStrategy interface more flexible if you want to support sorting arrays of different types. However, for this challenge, focusing on sorting arrays of numbers is sufficient.
• Think about how to make the Sorter class extensible so that new sorting strategies can be easily added in the future.
• The key to this problem is understanding how to decouple the sorting algorithm from the class that uses it, allowing for runtime selection of the algorithm.