Reputation: 2664

Sorting Algorithms - Methods

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?

Upvotes: 4

Answers (3)

Yakk - Adam Nevraumont

Reputation: 275200

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.

Upvotes: 2

andre

Reputation: 7249

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: