aseemgoyal's blog

By aseemgoyal, 10 years ago, In English

Implement a generic sorting algorithm i.e. the input array may contain int, double or structure values , or any type of data defined by user ?

The comparator will be defined by user . I thought to modify C++ sort , but stuck on the comparator .

EDIT : I want to implement my own function , not using sort() of C++ .

I came up with the below code but it is genereting errors :


#include <vector> #include <algorithm> #include <iostream> #include <string> #include <functional> using namespace std; class Person { public: // default constructor Person() : age(0) {} Person(int age, string name) { this->age = age; this->name = name; } int age; string name; }; // function object struct GreaterAge { bool operator()(const Person& a, const Person& b) { if(a.age == b.age) return a.name < b.name; return a.age > b.age; } }; template <class T> void Merge(T *a, int p, int q, int r , bool compare(const T& ,const T& )) { int i, j, k; const int n1 = q-p+1, n2 = r-q; int L[n1]; int R[n1]; for(i=0;i<n1;i++) L[i] = a[p+i]; for(j=0;j<n2;j++) R[j] = a[q+j+1]; for(k=p,i=j=0;k<=r;k++) { if(j>=n2 || (i<n1 && compare(L[i],R[j]))) a[k] = L[i++]; else //L[i]>R[j] { a[k] = R[j++]; } } } template <class T> void Merge_Sort(T *a, int p, int r , bool compare(const T& ,const T& )) { if(p<r) { int q = (p+r)/2; Merge_Sort(a,p,q,compare); Merge_Sort(a,q+1,r,compare); Merge(a,p,q,r,compare); } } int main() { Person arr[1000]; arr[0]=(Person(24,"Calvin")); arr[1]=(Person(30,"Benny")); arr[2]=(Person(30,"Alice")); arr[3]=(Person(28,"Alison")); arr[4]=(Person(20,"Rachna")); Merge_Sort(arr,0,4,GreaterAge); for(int i=0;i<5;i++) cout<<arr[i].age<<" "<<arr[i].name<<endl; return 0; }
  • Vote: I like it
  • -17
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

You can make a boolean operator in the struct itself in order to sort it in C++ sort like this

struct edge
{
    int from,to,cost;

    bool operator < (const edge e) const
    {
        return cost < e.cost;
    }
};

// sort(A,A+n);

or you can make an outer boolean function like this

struct edge
{
    int from,to,cost;
};

bool comparator(edge A, edge B)
{
    return A.cost < B.cost;
}

// sort(A,A+n, comparator);
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you want to use a function object instead of a function, you can add another class argument to your MergeSort templates, like in the standard sort template:

template <class T, class ST>
void Merge(T *a, int p, int q, int r, ST compare)
...
template <class T, class ST>
void Merge_Sort(T *a, int p, int r, ST compare)

After that, add empty parentheses to the function object parameter, like this:

    Merge_Sort(arr,0,4,GreaterAge());

Finally, arrays L and R should contain type T, not int, and the size of array R must be corrected:

	T L[n1];
	T R[n2];

After that, we finally get the desired output:

30  Alice
30  Benny
28  Alison
24  Calvin
20  Rachna
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi Gassa,
    thankyou , i am able to correct the code as you advised.
    I have some more doubts :

    1) as you see , i had poor code , can you suggest some tutorial/link from where i can understand the concept.

    2) Also , can we make "int" also more generic , because the input array can be actually a vector , so how to handle those cases ?

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. Just google the specific stuff you are having problem with.

      2. A more generic way to access containers in C++ is iterators.