generic sorting algorithm , not using sort()

[aseemgoyal]

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 .

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

[coder777]

The merge functions are supposed to look like this:

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

Line 79: you cannot provide a class name just an object:
Merge_Sort(arr,0,4,GreaterAge()); // Note ()


Line 40/41 are int, but should be T

[aseemgoyal]

yes, it worked , thanks for the fix.

Just wanted to know how to use iterators in templates , so that functions can be generic , for example consider input is a vector rather than an array.

Also , what if user do not define a compare() function ? std::sort() can handle this . How can it be achieved ?

[keskiverto]

std::sort has two versions (overloads). One takes comparator and the other does not. The latter is hardcoded to use operator< (of T).

[aseemgoyal]

last question : how to use iterators in templates , so that functions can be made generic , for example consider input is a vector instead of an array.

[coder777]

The problem is on line 40/41. You need to deduce the type of the data.
So you need a third parameter for the type:

template <class T, class TIterator, class TCompare>
void Merge_Sort(TIterator a_begin, TIterator a_end, int p, int q, int r , TCompare compare)

Call it like so:

std::vector<std::string> v;
...
Merge_Sort<Person>(v.begin(), v.end(),0,4,GreaterAge());

You might omit the r parameter because you might calculate it from the iterators. Not all iterator types allow this though