There’s an excellent course on Algorithms in the Coursera website. You should go check it out. It is a series of videos and exercises on several well known basal algorithms in Computer Science. If you are not a CS major, but you program as part of your daily routine, I recommend you at least watch the videos, since they are very informative.
Even though the language they use to implement the algorithms is Java, I decided it would be a good exercise for me to try them in C++. I am not particularly fond of C++, but I thought it would be an opportunity to explore more the language.
The first set of algorithms deal with sorting arrays of various types. I think that’s an excellent use case for the Strategy Design Pattern, in which each different sorting method is encapsulated into a subclass of a general ‘sorting’ class. This allows each strategy (method) to share the same outlets and they can be interchanged even at runtime if necessary.
Each individual strategy and its superclass Strategy class are all templates, to allow for sorting of different types of elements (double’s, int’s).
Each strategy will have a name() method that returns a string with the name of the method, a sort() method that does the trick, and a few other class methods.
Helper functions for a particular sorting method, should be kept private so we don’t contaminate the public scope of the strategies and possibly confuse the user of the class.
With the Strategy Pattern we can iterate over sorting strategies (like Selection Sort, Quick Sort, Merge Sort, etc).
In the following example, I have a simple test function called sorttest() that will take a strategy and an array of numbers (called ‘array’ in the code) and will test if the given strategy correctly sorts the array.
The sorting test for a vector of strategies can be done in one loop as is shown below:
for (typename vector<SortStrategy<T>*>::iterator aStrat = allStrats->begin();
aStrat != allStrats->end();
++aStrat)
{
T* data_copy = (T*)malloc(len*sizeof(*array));
memcpy(data_copy, array, len*sizeof(*array));
bool pass = sorttest(data_copy, len, *aStrat);
printf("Test%spassed.\n\n", pass ? " ": " not ");
}
In summary, the Strategy Design Pattern is very useful in cases when one task can be accomplished in many different ways and one wants to abstract the method to do the task. Pluggable classes are neat!
A copy of my code using the Strategy Pattern and the Sorting classes can be found in this repository https://github.com/martinberoiz/algorithms.
Martin Beroiz 