Sorting Algorithms and the Strategy Design Pattern

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.

Advertisements
Sorting Algorithms and the Strategy Design Pattern

The percolation problem

The percolation problem deals with connected paths between nodes in a 2D grid. The grid nodes could be in either of two states: “open” or “closed”; “conducting” or “insulating” or any other two opposite physical properties. When open, a node will connect with all the open nodes surrounding it. The system percolates where there is a path of connected nodes from any node on the top row to any node at the bottom row.

The system can be used to model diffusion of a liquid through a porous surface or the electric conductivity of a dielectric.

In the case of liquid diffusion, the grid is said to percolate when there is a connected path from any of the sites at the top row to any of the sites at the bottom row. On that moment, there is a free path for the liquid to move through the grid.

For a given grid size and a given fraction of open sites, there is a certain probability that the grid will percolate. It depends, of course, of the distribution of open sites on the grid.

It turns out that there is a phase transition on the probability of percolation of a two dimensional grid. Below a certain fraction of open sites, the probability of percolation is almost null. Above that fraction, the probability of percolation is almost certain. The percent value that divides both phases is very hard, if not impossible, to find theoretically. A good algorithm to simulate percolation for random grids is in need, to experimentally find this value.

The fast O(N lgN) algorithm to check for connected paths used in Sedgewick‘s Algorithm book is Quick Find or some optimized version of it.

I decided to implement myself these algorithms on C++, using the OO Strategy Pattern.

When I finished coding these command line tests, I thought it would be fun to see it in action for some concrete instance of a grid. That’s why I programmed a simple GUI for OS X.

The MVC (Model-View-Controller) was of great help here. Since I had my strategy classes for Quick Union, Quick Find and Weighted Quick Find as separate classes, I already had my model part done.

I then coded an Objective-C wrapper for the grid. This will be the class aware of the 2D nature of the grid. The model only knows about nodes, but it’s not spatially aware.

I only needed a general controller class, the application delegate provided by Xcode, and a view class to display the grid.

Once all the connections were done, I only added some bells and whistles to the app, and it was done.

An OS X GUI for a Percolation example
An OS X GUI for a Percolation example

I leave here a link to download the app, and I will post the source code in another post.

 

I hope you enjoy it!

The percolation problem