Strategy Pattern: Dynamic Sorting

This example demonstrates the Strategy pattern by implementing dynamic sorting algorithms. We define a `SortStrategy` interface and concrete implementations for different sorting algorithms (Bubble Sort, Quick Sort). The `Sorter` class uses a `SortStrategy` to sort a list of integers, allowing you to switch sorting algorithms at runtime.

The Core Idea: Strategy Pattern

The Strategy pattern allows you to define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from clients that use it. This promotes flexibility and avoids using conditional statements (if/else or switch) to select algorithms at runtime. Instead, you can inject or change the algorithm the client uses.

SortStrategy Interface

This interface defines the contract for all concrete sorting strategies. All sorting algorithms must implement this interface and provide their own `sort` method.

interface SortStrategy {
    List<Integer> sort(List<Integer> list);
}

Concrete Strategy: Bubble Sort

This class implements the `SortStrategy` interface using the Bubble Sort algorithm. It takes a list, sorts it in ascending order, and returns the sorted list. It creates a new list to avoid modifying the original.

class BubbleSort implements SortStrategy {
    @Override
    public List<Integer> sort(List<Integer> list) {
        List<Integer> sortedList = new ArrayList<>(list);
        int n = sortedList.size();
        for (int i = 0; i < n - 1; i++)
            for (int j = 0; j < n - i - 1; j++)
                if (sortedList.get(j) > sortedList.get(j + 1)) {
                    // swap temp and arr[i]
                    int temp = sortedList.get(j);
                    sortedList.set(j, sortedList.get(j + 1));
                    sortedList.set(j + 1, temp);
                }
        return sortedList;
    }
}

Concrete Strategy: Quick Sort

This class implements the `SortStrategy` interface using the Quick Sort algorithm. It also creates a new list and utilizes helper functions for partitioning and recursive sorting.

class QuickSort implements SortStrategy {
    @Override
    public List<Integer> sort(List<Integer> list) {
        List<Integer> sortedList = new ArrayList<>(list);
        quickSort(sortedList, 0, sortedList.size() - 1);
        return sortedList;
    }

    private void quickSort(List<Integer> list, int low, int high) {
        if (low < high) {
            int pi = partition(list, low, high);
            quickSort(list, low, pi - 1);
            quickSort(list, pi + 1, high);
        }
    }

    private int partition(List<Integer> list, int low, int high) {
        int pivot = list.get(high);
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (list.get(j) < pivot) {
                i++;
                int temp = list.get(i);
                list.set(i, list.get(j));
                list.set(j, temp);
            }
        }
        int temp = list.get(i + 1);
        list.set(i + 1, list.get(high));
        list.set(high, temp);
        return (i + 1);
    }
}

Context: Sorter Class

The `Sorter` class is the context. It holds a reference to a `SortStrategy` and uses it to perform the sorting. The `setStrategy` method allows you to change the sorting algorithm at runtime.

class Sorter {
    private SortStrategy strategy;

    public Sorter(SortStrategy strategy) {
        this.strategy = strategy;
    }

    public void setStrategy(SortStrategy strategy) {
        this.strategy = strategy;
    }

    public List<Integer> sort(List<Integer> list) {
        return strategy.sort(list);
    }
}

Client Code

This is the client code that uses the `Sorter` class with different strategies. It first creates a `Sorter` with `BubbleSort` and sorts the data. Then, it changes the strategy to `QuickSort` and sorts the data again. Notice the instantiation of new ArrayList<>(data), the original data list must remain unchanged.

public class StrategyPatternExample {
    public static void main(String[] args) {
        List<Integer> data = Arrays.asList(5, 2, 8, 1, 9, 4);

        // Using Bubble Sort
        Sorter sorter = new Sorter(new BubbleSort());
        List<Integer> sortedDataBubble = sorter.sort(new ArrayList<>(data));
        System.out.println("Sorted using Bubble Sort: " + sortedDataBubble);

        // Using Quick Sort
        sorter.setStrategy(new QuickSort());
        List<Integer> sortedDataQuick = sorter.sort(new ArrayList<>(data));
        System.out.println("Sorted using Quick Sort: " + sortedDataQuick);
    }
}

Real-Life Use Case

Imagine a payment processing system. You might have different strategies for processing payments: Credit Card, PayPal, Google Pay, etc. The system can dynamically switch between these strategies based on user preference or external factors (e.g., availability of a payment gateway).

Best Practices

• Favor composition over inheritance: The Strategy pattern uses composition to delegate the algorithm to a separate strategy object.
• Keep strategies simple: Each strategy should focus on a single, well-defined task.
• Consider using a factory: If you have many strategies, consider using a factory pattern to create and manage them.

Interview Tip

Be prepared to discuss the benefits of the Strategy pattern (flexibility, maintainability) and its drawbacks (increased number of classes). Also, be able to compare it to other behavioral patterns like Template Method or State.

When to Use the Strategy Pattern

Use the Strategy pattern when:

• You want to use different variants of an algorithm within an object.
• You have many related classes that differ only in their behavior.
• You need to choose algorithm implementations dynamically.
• You want to avoid using conditional statements to select different algorithms.

Memory Footprint

The Strategy pattern can increase the memory footprint slightly due to the additional strategy objects. However, the benefits of flexibility and maintainability often outweigh this cost.

Alternatives

Alternatives to the Strategy pattern include:

• Template Method: Use Template Method when the skeleton of the algorithm is fixed, but some steps vary.
• State: Use State when an object's behavior depends on its state and it must change its behavior at runtime.
• Simple conditional statements: In simple cases, conditional statements (if/else or switch) might be sufficient. However, this approach can become unmanageable as the number of algorithms grows.

Pros

• Flexibility: Easily switch between different algorithms at runtime.
• Maintainability: Each algorithm is encapsulated in its own class, making it easier to maintain and modify.
• Reusability: Strategies can be reused in different contexts.
• Open/Closed Principle: You can add new strategies without modifying the context class.

Cons

• Increased complexity: The pattern introduces additional classes, which can increase the overall complexity of the code.
• Client awareness: The client needs to be aware of the available strategies and choose the appropriate one.