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;
}
You can make a boolean operator in the struct itself in order to sort it in C++ sort like this
or you can make an outer boolean function like this
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:
After that, add empty parentheses to the function object parameter, like this:
Finally, arrays
L
andR
should contain typeT
, notint
, and the size of arrayR
must be corrected:After that, we finally get the desired output:
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 ?
Just google the specific stuff you are having problem with.
A more generic way to access containers in C++ is iterators.