Page 1 of 1

C++ Creating a general use sort class Rate Topic: -----

#1 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1148
  • View blog
  • Posts: 7,149
  • Joined: 07-September 06

Posted 11 November 2008 - 10:10 AM

Pre-Starting off
Hopefully you have read through these two tutorials, as it will make this tutorial shorter and easier to understand:
http://www.dreaminco...wtopic57199.htm
http://www.dreaminco...wtopic66970.htm

Starting off
In this tutorial we will be talking about how to create a templatized class to act as a sort class which will be able to sort an array of any objects quickly using my custom made quicksort function.

<edit>
NOTE - All the HTML tags (I believe) in the code should be replaced with b ) (without the space).
</edit>

Please remember to include this in the top of your C++ file:
#include<iostream>
using namespace std;


Setting up the sort class
We will want to get thr sort class out of the way first to give us an easy reference to look back at as we go.

So, we will begin by creating a templatized class called sort that takes a dataType (dT, also commonly seen as T), which containes a default constructor and desctuctor:
template<class dT> class Sort{
private:
public:
	Sort(void){
	}
	~Sort(void){
	}
};



NOTE - the word default in C++ means that it takes no arguments.

Once we have this we will want to get going with a sort function, however as the class is called sort we will be naming this function doSort (I know, very descriptive).

Here is what the function looks like:
	void doSort(dT* array, int low, int high, int(*sortFunction)(dT a, dT B)/>){
		int cLow = low;
		int cHigh = high;
		dT temp;
		dT x = array[(low + high) / 2];
		do{
			while (sortFunction(array[cLow], x) < 0){
				cLow++;
			}
			while (sortFunction(array[cHigh], x) > 0){
				cHigh--;
			}
			if (cLow <= cHigh){
				temp = array[cLow];
				array[cLow] = array[cHigh];
				array[cHigh] = temp;
				cLow++;
				cHigh--;
			}
		} while (cLow <= cHigh);
		if (low < cHigh){
			doSort(array, low, cHigh, sortFunction);
		}
		if (cLow < high){
			doSort(array, cLow, high, sortFunction);
		}
	}


Basically what it does is go through the array from the specified low index to the specified high index and sorts all the objects (or primitives) in the array between the two. The function also calls to itself recursively until it has finished sorting.

NOTICE - One of the parameters consists of this int(*sortFunction)(dT a, dT B), which you may not have seen yet. This is a function pointer (called sortFunction in this function (It can have any name, we are just calling it sortFunction)), which returns an int and takes 2 objects or primitives of type dT (or out templatized type). The reason for having a function pointer as the sortFunction is so you can tell it what you want the program to do when sorting an array of elements.

The only thing we have left to go is add a couple of default sort methods to the class so we can use the class easy later on.

	static int sortAsc(dT a, dT B)/>{
		return a-b;
	}
	static int sortDesc(dT a, dT B)/>{
		return b-a;
	}


Here is the full sort class:
template<class dT> class Sort{
private:
public:
	Sort(void){
	}
	~Sort(void){
	}
	void doSort(dT* array, int low, int high, int(*sortFunction)(dT a, dT B)/>){
		int cLow = low;
		int cHigh = high;
		dT temp;
		dT x = array[(low + high) / 2];
		do{
			while (sortFunction(array[cLow], x) < 0){
				cLow++;
			}
			while (sortFunction(array[cHigh], x) > 0){
				cHigh--;
			}
			if (cLow <= cHigh){
				temp = array[cLow];
				array[cLow] = array[cHigh];
				array[cHigh] = temp;
				cLow++;
				cHigh--;
			}
		} while (cLow <= cHigh);
		if (low < cHigh){
			doSort(array, low, cHigh, sortFunction);
		}
		if (cLow < high){
			doSort(array, cLow, high, sortFunction);
		}
	}

	static int sortAsc(dT a, dT B)/>{
		return a-b;
	}
	static int sortDesc(dT a, dT B)/>{
		return b-a;
	}
};


Setting up the main
Now we will go through and set up the main function to create an array of integers and then sort them and output the sorted array.

NOTE - You can easily change how the array is sorted by changing the sortFunction called.

Here is the whole creation of the array and setting its values:
int main(){
	const int maxLength = 10;
	int a[maxLength];
	for(int i=0; i<maxLength; i++){
		if(i%10 == 0){
			cout << endl;
		}
		a[i] = rand();
	}
	return 0;
}


Now, we want to sort the array and then output the sorted array after it is finished.

That can be done by adding this to the main function:
	typedef Sort<int> sInt;
	sInt* s = new sInt();
	s->doSort(a, 0, maxLength-1, sInt::sortAsc);
	cout << "Sorted array: " << endl;
	for(int i=0; i<maxLength; i++){
		if(i%10 == 0){
			cout << endl;
		}
		cout << a[i] << "\t";
	}


NOTICE - We are calling to sInt::sortAsc as the sortFunction we are passing to the sort class. This means that it will be sorting each element of the array based on if a-b <- both of which are integers; is greater than or less than 0.

Here is a copy of the whole main program at thsi point:
#include<iostream>
using namespace std;

template<class dT> class Sort{
private:
public:
	Sort(void){
	}
	~Sort(void){
	}
	void doSort(dT* array, int low, int high, int(*sortFunction)(dT a, dT B)/>){
		int cLow = low;
		int cHigh = high;
		dT temp;
		dT x = array[(low + high) / 2];
		do{
			while (sortFunction(array[cLow], x) < 0){
				cLow++;
			}
			while (sortFunction(array[cHigh], x) > 0){
				cHigh--;
			}
			if (cLow <= cHigh){
				temp = array[cLow];
				array[cLow] = array[cHigh];
				array[cHigh] = temp;
				cLow++;
				cHigh--;
			}
		} while (cLow <= cHigh);
		if (low < cHigh){
			doSort(array, low, cHigh, sortFunction);
		}
		if (cLow < high){
			doSort(array, cLow, high, sortFunction);
		}
	}

	static int sortAsc(dT a, dT B)/>{
		return a-b;
	}
	static int sortDesc(dT a, dT B)/>{
		return b-a;
	}
};

int main(){
	const int maxLength = 10;
	int a[maxLength];
	for(int i=0; i<maxLength; i++){
		if(i%10 == 0){
			cout << endl;
		}
		a[i] = rand();
	}
	typedef Sort<int> sInt;
	sInt* s = new sInt();
	s->doSort(a, 0, maxLength-1, sInt::sortAsc);
	cout << "Sorted array: " << endl;
	for(int i=0; i<maxLength; i++){
		if(i%10 == 0){
			cout << endl;
		}
		cout << a[i] << "\t";
	}
	return 0;
}


Sorting an array of objects
At this point we will look at sorting an array of objects (for which we will use a premade simple object that conatains a double.

Here is the premade code:
class tItem{
private:
	double value;
public:
	tItem(void){
		value = 0;
	}
	~tItem(void){
	}
	void setValue(double val){
		value = val;
	}
	double getValue(void){
		return value;
	}
	int operator-(tItem B)/>{
		double v = b.getValue();
		if(value > v){
			return 1;
		}
		else if(value < v){
			return -1;
		}
		return 0;
	}
};


NOTICE - The subtraction operator has been overloaded so the sort class can continue using its default functions for sorting.

Here is a new version of the whole program which uses and sorts an array of tItems;

#include<iostream>
using namespace std;

template<class dT> class Sort{
private:
public:
	Sort(void){
	}
	~Sort(void){
	}
	void doSort(dT* array, int low, int high, int(*sortFunction)(dT a, dT B)/>){
		int cLow = low;
		int cHigh = high;
		dT temp;
		dT x = array[(low + high) / 2];
		do{
			while (sortFunction(array[cLow], x) < 0){
				cLow++;
			}
			while (sortFunction(array[cHigh], x) > 0){
				cHigh--;
			}
			if (cLow <= cHigh){
				temp = array[cLow];
				array[cLow] = array[cHigh];
				array[cHigh] = temp;
				cLow++;
				cHigh--;
			}
		} while (cLow <= cHigh);
		if (low < cHigh){
			doSort(array, low, cHigh, sortFunction);
		}
		if (cLow < high){
			doSort(array, cLow, high, sortFunction);
		}
	}

	static int sortAsc(dT a, dT B)/>{
		return a-b;
	}
	static int sortDesc(dT a, dT B)/>{
		return b-a;
	}
};

class tItem{
private:
	double value;
public:
	tItem(void){
		value = 0;
	}
	~tItem(void){
	}
	void setValue(double val){
		value = val;
	}
	double getValue(void){
		return value;
	}
	int operator-(tItem B)/>{
		double v = b.getValue();
		if(value > v){
			return 1;
		}
		else if(value < v){
			return -1;
		}
		return 0;
	}
};

int main(){
	typedef Sort<tItem> sItem;
	const int maxLength = 10;
	tItem a[maxLength];
	for(int i=0; i<maxLength; i++){
		if(i%10 == 0){
			cout << endl;
		}
		a[i].setValue(rand()%256);
		cout << a[i].getValue() << "\t";
	}
	sItem* s = new sItem();
	s->doSort(a, 0, maxLength-1, sItem::sortAsc);
	cout << "Sorted array: " << endl;
	for(int i=0; i<maxLength; i++){
		if(i%10 == 0){
			cout << endl;
		}
		cout << a[i].getValue() << "\t";
	}
	return 0;
}


NOTE - You can overload any operator you wish to for your sort functions you just have to create a different function to do the actual sort comparison.

Looking into creating a custom sort comparison
This will require a little bit of re-working for the rest of the code, but it will allow for more flexibility and the simplification of the tItem subtraction operator.

First off lets create a new function to act as our sort comparison function and have it return a double (instead of the default ints we have the sort class comparison functions returning).

double customSorter(tItem a, tItem B)/>{
	return a-b;
}


Now we need to change the template on our sort class to allow for a second dataType, which we will call rT standing for return Type.

template<class dT, class rT> class Sort{


And now we need to make some use of the new return Type, so lets allow for the sortFunction to return whatever is in rT:
void doSort(dT* array, int low, int high, rT(*sortFunction)(dT a, dT B)/>){


At this point we are able to implement the new sort call, so here is the full code once again:
#include<iostream>
using namespace std;

template<class dT, class rT> class Sort{
private:
public:
	Sort(void){
	}
	~Sort(void){
	}
	void doSort(dT* array, int low, int high, rT(*sortFunction)(dT a, dT B)/>){
		int cLow = low;
		int cHigh = high;
		dT temp;
		dT x = array[(low + high) / 2];
		do{
			while (sortFunction(array[cLow], x) < 0){
				cLow++;
			}
			while (sortFunction(array[cHigh], x) > 0){
				cHigh--;
			}
			if (cLow <= cHigh){
				temp = array[cLow];
				array[cLow] = array[cHigh];
				array[cHigh] = temp;
				cLow++;
				cHigh--;
			}
		} while (cLow <= cHigh);
		if (low < cHigh){
			doSort(array, low, cHigh, sortFunction);
		}
		if (cLow < high){
			doSort(array, cLow, high, sortFunction);
		}
	}

	static int sortAsc(dT a, dT B)/>{
		return a-b;
	}
	static int sortDesc(dT a, dT B)/>{
		return b-a;
	}
};

class tItem{
private:
	double value;
public:
	tItem(void){
		value = 0;
	}
	~tItem(void){
	}
	void setValue(double val){
		value = val;
	}
	double getValue(void){
		return value;
	}
	int operator-(tItem B)/>{
		double v = b.getValue();
		if(value > v){
			return 1;
		}
		else if(value < v){
			return -1;
		}
		return 0;
	}
};

double customSorter(tItem a, tItem B)/>{
	return a-b;
}

int main(){
	typedef Sort<tItem, double> sItem;
	const int maxLength = 10;
	tItem a[maxLength];
	for(int i=0; i<maxLength; i++){
		if(i%10 == 0){
			cout << endl;
		}
		a[i].setValue(rand()%256);
		cout << a[i].getValue() << "\t";
	}
	sItem* s = new sItem();
	s->doSort(a, 0, maxLength-1, customSorter);
	cout << "Sorted array: " << endl;
	for(int i=0; i<maxLength; i++){
		if(i%10 == 0){
			cout << endl;
		}
		cout << a[i].getValue() << "\t";
	}
	return 0;
}


Ending
Hopefully that helped you to see how versitile C++ can be (if you didn't know already) and shed some light on how to create a custom sort class that can be used for any object or primitive datatype.

Enjoy.

Is This A Good Question/Topic? 0
  • +

Page 1 of 1