# Project Kenneth # Implementing an Algorithm Selector: The Usual, The Okay and The Complicated

This post is part of a series that explores how flexible programming languages and frameworks can get. We all know that with any given task, there are several approaches available to achieve it. Let's look at this in action!

In this post, we will look at the different approaches in implementing an Algorithm Selector. For this article’s purposes, an Algorithm Selector is basically a method or class that determines which appropriate algorithm is best used for a certain input.

Let's say that I want to implement an Algorithm Selector for sorting algorithms. To select the correct algorithm you'll use, I'll base it on the length of the array:

• For smaller arrays, I decided to use Bubble Sort.
• For larger arrays, I want to use Quick Sort.

In this example, let's set the threshold to 100. Any array with more than 100 items will be considered a "large" array.

Of course, there's probably more than 3 ways to ways to do this in Java (or any OOP language for that matter), but, I carefully selected three unique ones that better matches the ff. categories: The Usual, The Okay, and The Complicated.

## The Usual

``````private int[] sort(int[] arrToSort) {
if (arrToSort.length <= 100) {
return this.bubbleSort(arrToSort);
}

return this.quickSort(arrToSort);
}

public void execute() {
var fiftyArray = Helpers.generateArray(50);
var hundredFiftyArray = Helpers.generateArray(150);

this.sort(fiftyArray); // bubble sort
this.sort(hundredFiftyArray); // quick sort
}
``````

In the above implementation, I simply used an `if` statement to determine the correct algorithm to use. Pretty straightforward and it just works. Let's step it up a bit.

## The Okay

``````private int[] sort(int[] arrToSort) {
var sortingAlgos = new ISortingAlgorithm[] {
new BubbleSort(),
new QuickSort()
};

var canSort = false;
var i = 0;
do {
canSort = sortingAlgos[i].canSort(arrToSort);

if (canSort) {
return sortingAlgos[i].sort(arrToSort);
}

i++;
} while (!canSort && i < sortingAlgos.length);

return arrToSort;
}

public void execute() {
var fiftyArray = Helpers.generateArray(50);
var hundredFiftyArray = Helpers.generateArray(150);

this.sort(fiftyArray); // bubble sort
this.sort(hundredFiftyArray); // quick sort
}
``````

Now we're onto something. I've modified the `sort` method to use a more flexible way of identifying the best algorithm to use. Instead of hardcoding using an `if` statement, all sorting algorithms are implemented in their own class. These algorithm classes implements the `ISortingAlgorithm` interface.

``````public interface ISortingAlgorithm {
int[] sort(int[] arrToSort);
boolean canSort(int[] arrToSort);
}
``````

This interface exposes a `canSort` method so any class implementation bears the responsibility of checking the input and ultimately declaring "Hey, I'm the one for this array!". A bit cheesy but you get how it works. Additionally, the actual sorting logic (`sort` method) is implemented inside each algorithm class.

Here's how this looks like for the `BubbleSort` class:

``````public class BubbleSort implements ISortingAlgorithm {

@Override
public int[] sort(int[] arrToSort) {
System.out.println("Sorted " + arrToSort.length+ " items by bubble sort!");
// Implement quick sort

return arrToSort;
}

@Override
public boolean canSort(int[] arrToSort) {
return arrToSort.length <= 100;
}
}
``````

The `sort` method will then iterate over the array of algorithms. Then, the first one to return `true` when their `canSort` method is called will be the algorithm used to sort the input array.

That's quite a bit already, right? Well, let's look at something more exciting.

## The Complicated

The problem with The Okay approach is that the sorting algorithms are tightly coupled with the executing class. All of them are explicitly instantiated inside the `sort` method. In terms of good OOP design, it's not recommended to have very tight coupling between classes.

So in this approach, we'll use the Chain of Responsibility design pattern. In this pattern, there's a set of receivers with which the input will pass through. In a few points, here's how this pattern works:

2. If the receiver determines that the input is compatible with it, the receiver will proceed with the actual processing.
3. If the input is not compatible with the receiver, the current receiver will just pass the input to the next available receiver.

For this article, the "receivers" are the sorting algorithm classes. I've now modified them to extend the `SortingAlgorithm` class:

``````public abstract class SortingAlgorithm {
private SortingAlgorithm NextAlgo = null;

public SortingAlgorithm() {
}

public SortingAlgorithm(SortingAlgorithm NextAlgo) {
this.NextAlgo = NextAlgo;
}

protected abstract boolean canSort(int[] arrToSort);

protected abstract int[] sortInternal(int[] arrToSort);

public int[] sort(int[] arrToSort) {
if (this.canSort(arrToSort)) {
return this.sortInternal(arrToSort);
} else if (this.NextAlgo != null) {
return this.NextAlgo.sort(arrToSort);
} else {
return arrToSort;
}
}
}
``````

As seen above, the `SortingAlgorithm` class optionally receives the `NextAlgo`. This is the next algorithm in the chain and it will be called upon if the current algorithm cannot process the input. For simplicity, if there's no available `NextAlgo`, the `sort` method will just return the unprocessed input.

Now, let's look at the actual execution using this approach:

``````var fiftyArray = Helpers.generateArray(50);
var hundredFiftyArray = Helpers.generateArray(150);

var quickSort = new QuickSort();
var bubbleSort = new BubbleSort(quickSort);

var sortChain = new SortingChain(bubbleSort);

sortChain.sort(fiftyArray); // bubble sort
sortChain.sort(hundredFiftyArray); // quick sort
``````

In the above execution code, the sorting algorithms are actually instantiated outside the algorithm selector class `SortingChain`. Now, if I need to add/remove sorting algorithms , I don't need to touch the `SortingChain` class.

If you want to step this up further, you can also use Dependency Injection to dynamically load the sorting algorithms. Additionally, there are other design patterns aside from Chain of Responsibility that can be used to achieve the same thing.

## The End

For your reference, all the code for this post can be found here.

Anyway, there's most likely lots of approaches to implementing an Algorithm Selector. Feel free to share them by commenting on this post.

I hoped you enjoyed exploring these with me. I'll be posting more in this series (covering other programming languages too!) so make sure to keep an eye!