Design Sorting algorithm using Strategy Design Pattern

September 25, 2015 / Behavioral Design Patterns, Design Patterns, Strategy Design Pattern / By

What is a Strategy?

Strategy is a plan of action designed to achieve a long-term or overall aim.

Behaviour of a class / Algorithm depends upon the strategy they use to covert Input to Output.

Algorithm with Strategy

If Strategy is tightly bonded with the Algorithm/Class then variation in Strategy leads in Different version of Algorithm.

Lets understand by example,

Frequently Asked:

[showads ad=inside_post]

Suppose our requirement is to design an Algorithm to sort numbers in Ascending order. In such scenario,

Algorithm : Sorting in Ascending Order

Strategy : Comparison of two numbers a and b will return a if a < b.

Lets look at the code,

class AsscendingSortAlgo
{

	void swap(int &x, int &y)
	{
        int tmp = x;
	    x = y;
		y = tmp;
	}
	bool comparisionLogic(int a, int b)
	{
		if(a > b)
			return true;
		else
			return false;
	}
public:
	void sort(std::vector<int> & arr) {

	      bool isSwapped = true;
	      int x = 0;
	      while (isSwapped)
	      {
	            isSwapped = false;
	            x++;
	            for (int i = 0; i < arr.size() - x; i++)
	            {
	                  if (comparisionLogic(arr[i] , arr[i + 1]) )
	                  {
	                	  	swap(arr[i], arr[i + 1]);
	                        isSwapped = true;
	                  }
	            }
	      }
	}

};

Now lets increase our requirements, now we also want to design an Algorithm to sort numbers in Descending order. In such scenario,

Algorithm : Sorting in Descending Order

Strategy : Comparison of two numbers a and b will return b if a < b.

Lets look at the code,

class DessendingSortAlgo
{

	void swap(int &x, int &y)
	{
        int tmp = x;
	    x = y;
		y = tmp;
	}
	bool comparisionLogic(int a, int b)
	{
		if(a < b)
			return true;
		else
			return false;
	}
public:
	void sort(std::vector<int> & arr) {

	      bool isSwapped = true;
	      int x = 0;
	      while (isSwapped)
	      {
	            isSwapped = false;
	            x++;
	            for (int i = 0; i < arr.size() - x; i++)
	            {
	                  if (comparisionLogic(arr[i] , arr[i + 1]) )
	                  {
	                	swap(arr[i], arr[i + 1]);
	                        isSwapped = true;
	                  }
	            }
	      }
	}

};

This shows with this kind of Design on change of requirement, we need to add different classes.

Internally algorithm of both the above classes are same, its actually their Strategy that is different i.e. comparison logic. Because Strategy is tightly bonded with Algorithm therefore little change in comparison function (Strategy) results in different class.

How to correct this design ?

Answer is using Strategy Design Pattern.

Intent of Strategy Design Pattern

  •  Define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from the clients that use it.
  • Capture the abstraction in an interface, bury implementation details in derived classes.

Implementation of Strategy Design Pattern

  • Create an Abstract Strategy interface defining an action
  • Inherit Concrete strategy classes from Abstract Strategy interface.
  • Create an Algorithm class and loosely bind Strategy with it i.e. Create a pointer/ reference of Abstract Strategy in algorithm class.
  • Provide mechanism to assign Concrete Strategy to Algorithm class at run time.

Strategy Design Pattern

Implementing strategy design pattern in sorting algorithm

 

Designing Sorting algorithm with Strategy Design pattern

Create Abstract Strategy i.e. Abstract Comparator Interface

class IComparator
{
public:
	virtual bool compare(int a, int b) = 0;
	virtual ~IComparator(){}
};

Create Concrete Strategy classes i.e. Lesser Comparator and Greater Comparator,

class LesserComprataor : public IComparator
{
public:
	bool compare(int a, int b)
	{
		if(a > b)
			return true;
		else
			return false;
	}
};
class GreaterComprataor : public IComparator
{
public:
	bool compare(int a, int b)
	{
		if(a < b)
			return true;
		else
			return false;
	}
};

Create an algorithm class – Sorting class with loose binding with Comparator,

class SortingAlgo
{

	IComparator * m_pComparator;
	void swap(int &x, int &y)
	{
        int tmp = x;
	    x = y;
		y = tmp;
	}
public:
	SortingAlgo()
	{
		m_pComparator = new LesserComprataor();
	}
	void sort(std::vector<int> & arr, IComparator * pComparator = NULL)
	{
		  if(pComparator == NULL)
			pComparator = m_pComparator;

		  bool isSwapped = true;
	      int x = 0;
	      while (isSwapped)
	      {
	            isSwapped = false;
	            x++;
	            for (int i = 0; i < arr.size() - x; i++)
	            {
	                  if (pComparator->compare(arr[i] , arr[i + 1]) )
	                  {
	                	  	swap(arr[i], arr[i + 1]);
	                        isSwapped = true;
	                  }
	            }
	      }
	}

};

Using this Sorting class and different Comparators to achieve our result.

std::vector<int> arr = {1,5,2,4,3};
	SortingAlgo obj;
	IComparator * pComp = new LesserComprataor();
	obj.sort(arr, pComp);
	for (int var = 0; var < 5; ++var) {
		std::cout<<arr[var]<<" ";
	}
	std::cout<<std::endl;
	delete pComp;
	pComp = NULL;

	pComp = new GreaterComprataor();
	obj.sort(arr, pComp);
	for (int var = 0; var < 5; ++var) {
		std::cout<<arr[var]<<" ";
	}
	std::cout<<std::endl;
	delete pComp;
	pComp = NULL;

	delete pComp;
	pComp = NULL;

	obj.sort(arr);
	for (int var = 0; var < 5; ++var) {
		std::cout<<arr[var]<<" ";
	}
	std::cout<<std::endl;
	delete pComp;
	pComp = NULL;

Thanks & Happy Designing.

Complete executable code is as follows,

[code language=”cpp” collapse=”true”]

#include <iostream>
#include <vector>

class IComparator
{
public:
virtual bool compare(int a, int b) = 0;
virtual ~IComparator(){}
};

class LesserComprataor : public IComparator
{
public:
bool compare(int a, int b)
{
if(a > b)
return true;
else
return false;
}
};
class GreaterComprataor : public IComparator
{
public:
bool compare(int a, int b)
{
if(a < b)
return true;
else
return false;
}
};

class SortingAlgo
{

IComparator * m_pComparator;
void swap(int &x, int &y)
{
int tmp = x;
x = y;
y = tmp;
}
public:
SortingAlgo()
{
m_pComparator = new LesserComprataor();
}
void sort(std::vector<int> & arr, IComparator * pComparator = NULL)
{
if(pComparator == NULL)
pComparator = m_pComparator;

bool isSwapped = true;
int x = 0;
while (isSwapped)
{
isSwapped = false;
x++;
for (int i = 0; i < arr.size() – x; i++)
{
if (pComparator->compare(arr[i] , arr[i + 1]) )
{
swap(arr[i], arr[i + 1]);
isSwapped = true;
}
}
}
}

};

int main()
{
std::vector<int> arr = {1,5,2,4,3};
SortingAlgo obj;
IComparator * pComp = new LesserComprataor();
obj.sort(arr, pComp);
for (int var = 0; var < 5; ++var) {
std::cout<<arr[var]<<" ";
}
std::cout<<std::endl;
delete pComp;
pComp = NULL;

pComp = new GreaterComprataor();
obj.sort(arr, pComp);
for (int var = 0; var < 5; ++var) {
std::cout<<arr[var]<<" ";
}
std::cout<<std::endl;
delete pComp;
pComp = NULL;

delete pComp;
pComp = NULL;

obj.sort(arr);
for (int var = 0; var < 5; ++var) {
std::cout<<arr[var]<<" ";
}
std::cout<<std::endl;
delete pComp;
pComp = NULL;

return 0;
}

[/code]

Related posts:

  1. Learn State Design Pattern by Designing a Simple Music System
  2. Binary Tree Traversal with Strategy design pattern and open-closed principle
  3. Designing a Configurable Logging framework using Observer Design Pattern
  4. Task Grouping Using Composite Design Pattern
  5. Designing Event Handling Framework using Command Design Pattern
  6. Designing a Multiton: Singleton that returns 5 objects in cycle
  7. Need of Factory Method Design Pattern in Frameworks Explained
  8. Designing a Board Game (Mastermind) in C++ using MVC, State and Observer Design Patterns

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top