aseemgoyal's blog

How to implement "Generic" sorting algorithm ?

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

Comments Comments (4)
| 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);
→ Reply
»
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
→ Reply
  • »
    »
    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 ?

    → Reply
    • »
      »
      »
      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.

      → Reply