CODEWITHSUNDEEP
c++algorithmsortingpolymorphism
Guyute
Guyute

Reputation: 149

I need help understanding a programming challenge

I am trying to do some homework and cannot wrap my head around a question. I have posted in the classes discussion board and emailed the professor but am not getting any help.

The question is: Design a class abstractSort that can be used to analyze the number of comparisons performed by a sorting algorithm. The class should have a member function compare that is capable of comparing two array elements, and a means of keeping track of the number of comparisons performed. The class should be an abstract class with a pure virtual member function

virtual void Sort(int arr[], int size)= 0;

which, when overridden, will sort the array by calling the compare function to determine with the relative order of pairs of numbers (that is the phrase I don't get). Create a subclass of AbstractSort that uses a simple sorting algorithm to implement the sort function. The class should have a member function that can be called after the sorting is done to determine the number of comparisons performed.

I have an idea of how to code this but I just don't think that I am going about it the way the question is worded. I have written code to keep track of comparisons by incrementing a counter and outputting that number. The question is bugging me however. What does the author mean by saying "by calling the compare function to determine with the relative order of pairs of numbers "

Does anybody have any idea of what they mean? am I just over complicating an obvious question or is there some subtle challenge to this that I don't see. As I stated I do not need help coding the problem, just understanding the question.

Upvotes: 3

Views: 649

Answers (1)

Aasmund Eldhuset
Aasmund Eldhuset

Reputation: 37950

At some point during an ordinary implementation of most sorting algorithms, you'd have something like this:

if (elements[i] < elements[j]) {
    // Do something
}
else {
    // Do something else
}

It is often convenient to "outsource" the job of comparing the elements to a separate function (I'm assuming for simplicity that the elements being sorted are integers):

protected:
bool isSmaller(int a, int b) {
    return a < b;
}

// Inside sorting function:
if (isSmaller(elements[i], elements[j])) { ... } else { ... }

Combined with inheritance, you could define isSmaller() in a base class, and for each sorting algorithm you'd like to implement (quick sort, merge sort, insertion sort...), you'd create a new subclass. However, each subclass should call isSmaller() rather than using < to determine which elements should come before which. Then, you can add your "count the number of comparisions" code (which, as you say, would consist of simply incrementing a counter) to isSmaller().

(The point of the task is to make you realize that inheritance can free you from having to duplicate the counting code in every sorting algorithm implementation. Also, when using function pointers or function objects, the idea of "outsourcing" the comparison can also be used to make a "configurable" sorting class where the user of the class can decide how comparisons are to be performed, in order to e.g. sort numbers descendingly, or to sort a list of persons based on their names, etc.)

Upvotes: 4

Related Questions