Sorting Algorithms - Methods

Question

I need to implement three different sorting algorithms using an object-oriented approach, and I was thinking of a better method to deal with this.

Basically, I think it should look like this:

-> Sort (class, interface, polymorphic)

Inheritance:

-> Sort bubbles

-> Insert Sort

-> QuickSort

If each of the views has the same interface, it would be easier to access different sorting methods, and this means that when I come to add other sorting algorithms, I can easily implement them in the current design and class structure.

My questions:

• Is this a good approach to use?

• Is it possible to use templates? That is, if I wanted to use Bubble, he would call sorting the bubbles, if I wanted to use Insertion, would this call Insertion?

Answer 1

As suggested using the interface (pure virtual class)

Interface Method:

class sort_algorithm_interface { public: virtual void sort(std::vector<int>& input) const = 0; }; class BubbleSort : public sort_algorithm_interface { public: virtual void sort(std::vector<int>& input) const {/* sort the input */} }; class InsertionSort: public sort_algorithm_interface { public: virtual void sort(std::vector<int>& input) const {/* sort the input */} }; class QuickSort: public sort_algorithm_interface { public: virtual void sort(std::vector<int>& input) const {/* sort the input */} }; 

Now that you want to sort you, follow these steps:

 sort_algorithm_interface& s = QuickSort(input); s.sort(input); 

Template Method:

 class BubbleSort { public: void sort(std::vector<int>& input) const {/* sort the input */} }; class InsertionSort { public: void sort(std::vector<int>& input) const {/* sort the input */} }; class QuickSort { public: void sort(std::vector<int>& input) const {/* sort the input */} }; template<typename Sort> class MySort { void sort(std::vector<int>& input) { Sort s; s.sort(begin, end); } } 

Used as follows:

 MySort<QuickSort> s; s.sort(input); 

Answer 2

Sort should be an interface or an abstract class, while bubble / insertion / quick-sort should be implementations / concrete classes.

Also worth knowing about the following:

Strategy:

http://en.wikipedia.org/wiki/Strategy_pattern

and

Status Template:

http://en.wikipedia.org/wiki/State_pattern

As for the templates, I don’t think it is worth it in your case.

Answer 3

The right way to do this in C ++ is through templates.

Sorting something is an algorithm, and it usually has almost no permanent state. Sorting is not an object - it is a function for data (which can be objects).

The std library already has sorting with this signature:

 template<typename I, typename C = std::less<typename std::iterator_traits<I>::value_type> > void sort(I begin, I end, C comp = C()); 

The begin and end iterators denote the range of values ​​to be sorted, and comp is a functor (or function) that, when passing two elements of the range of values, indicates whether the first of them is smaller than the second.

To use this in std::vector , you would do something like this:

 std::vector<int> myVector; // assume it has some data in it sort( myVector.begin(), myVector.end() ); 

std :: sort (usually?) - quicksort. But the interface works for quick, bubble and sort insertion.

A big advantage of this approach is that one species can use the other. As an example, while quicksort is faster on large datasets, often on small datasets it is easy to sort the insert (lower constant coefficient, even with an overhead of n ^ 2). Thus, by writing down these types, quicksort recursive calls can instead be inserted into sorting when the number of items is small.

Now, if you need a temporary replacement for the algorithm that you are using, you will need to indicate which iterators you are using, and possibly even which comparator. This can be done either with a common function signature (what I would do), or with a base class with a clean virtual interface (which I would advise). Note that the overhead for the selected comparison time is not trivial. Overhead from a fixed iterator selection or from calling a function pointer or a virtual method, if it is not executed when recursive calls to your algorithm, will be quite cheap for any container of a reasonable size.