Sorting Algorithms - Methods

Question

I have to implement three different sorting algorithms using an Object-Oriented Approach and I have been thinking of the best method to combat this.

Basically, I think it should look like this:

-> Sort (Class, interface, Polymorphic)

Inherit:

-> Bubble Sort

-> Insertion Sort

-> QuickSort

If each of the sorts have the same interface then it would be easier to access the different methods of sorting, thus, meaning that when I come to add other sorting algorithms, I can easily implement them into the current design and class structure.

My questions are:

Is this a good approach to use?
Is there scope for me to use Templates? I.e. if I wanted to use Bubble, it would call the bubble sort, if I wanted to use Insertion it would call Insertion?

sampson-chen · Accepted Answer · 2012-10-30 14:35:20Z

5

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

It's also worth learning about the following:

Strategy Pattern:

Strategy Pattern Diagram http://en.wikipedia.org/wiki/Strategy_pattern

and

State Pattern:

State Pattern Diagram

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

As for templates, I don't think it's worth it in your case.

edited Oct 30, 2012 at 14:35

answered Oct 30, 2012 at 14:30

sampson-chen

47.6k13 gold badges87 silver badges81 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

andre · Accepted Answer · 2012-11-01 15:11:09Z

3

As suggested use an 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 when you want to sort you simple do the following:

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);
    }
}

This is used as follows:

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

edited Nov 1, 2012 at 15:11

answered Oct 30, 2012 at 14:34

andre

7,2856 gold badges50 silver badges80 bronze badges

11 Comments

Phorce Over a year ago

Thank you :) In "algorithm" would I need to create/ objects for each of the bubble sort, insertion sorts etc..? ... I would like to use Templates, if not for triggering which sort to compute but the data type of the sorted data

Phorce Over a year ago

Thank you :)! So for the Template method, BubbleSort etc.. will still inherit from Sort?

andre Over a year ago

Nope, sort_algorithm_interface does not need anything else. You only need to add code where is says /* sort the input */.

Phorce Over a year ago

Just to clarify, I can implement the 'Template Method' without the use of creating an abstract class?

andre Over a year ago

@Phorce The template method is a bit cleaner for me. But that's just a personal choice. It depends on what you prefer.

|

Yakk - Adam Nevraumont · Accepted Answer · 2012-11-01 15:32:43Z

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

Sorting something is an algorithm, and it generally has little to no persistent state. A sort isn't an object -- it is a function on data (which may be objects).

The std library already has a sort, 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 iterators begin and end denote a range of values to be sorted, and comp is a functor (or function) that when passed two elements of the range of values tells you if the first one is less than the second.

To use this on a std::vector, you'd do something like this:

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

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

The big advantage of this approach is that one sort can use another. As an example, while a quicksort is faster on large data sets, often on small data sets the simplicity of insertion sort wins (lower constant factor, even with the n^2 overhead). So by writing your sorts like this, quicksort's recursive calls can instead become insertion sort when the number of elements is small.

Now, if you need run-time substitution of which algorithm you are using, you'll need to pin down what iterators you are using, and maybe even what comparitor. This can be done with either a common function signature (what I'd do), or a base class with a pure virtual interface (which I would advise against). Note that the overhead for a run-time chosen comparitor is non-trivial, however. The overhead from a fixed iterator choice, or from a pointer-to-function or virtual method call, so long as it isn't done in the recursive calls of your algorithm, will be pretty cheap for any reasonable sized container.

Collectives™ on Stack Overflow

Sorting Algorithms - Methods

3 Answers 3

Comments

11 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

11 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related