Quicksort array of class objects

Dev Shed Forums Sponsor:

March 23rd, 2005, 10:07 AM

Voelcker

Contributing User

Join Date: Sep 2004

Location: Maryland

Posts: 225

Time spent in forums: 1 Day 21 h 51 m 59 sec
Reputation Power: 9

Quicksort array of class objects

I'm working on yet another class project. To give some back ground, I have to modify a previous project to sort a dynamically sized array using a quicksort algorithm, and the quicksort function must be a template function so it could sort arrays of any data type.

The original project involved reading in a list of names from a file and adding them to a dynamically sized array of class objects. Each array item is an instance of class Name. That project works flawlessly and I'm not as concerned with the original project as I am changing the implementation to sort the array of class objects.

On the class discussions there is a quicksort function and swap function that looks like:

Code:

void Swap ( int &First, int &Second )
{
	int Temp = First;
	First = Second;
	Second = Temp;
}

void QuickSort  ( int Data[], int Size )
{
	if ( Size > 1 )
	{
		if ( Size == 2 )
		{
			if ( Data[0] > Data[1] )
				Swap ( Data[0], Data[1] );
		}
		else
		{
			int Pivot = Size / 2, Partition1 = -1, Partition2 = Size;
			while ( Partition1 < Pivot && Data[++Partition1] <= Data[Pivot] )
				;
			while ( Partition2 > Pivot && Data[--Partition2] > Data[Pivot] )
				;
			while ( Partition1 != Pivot || Partition2 != Pivot )
			{
				swap ( Data [Partition1], Data [Partition2] );				
				if ( Partition1 == Pivot )
				{
					Pivot = Partition2;
					while ( Partition1 < Pivot &&
							     Data[++Partition1] <= Data[Pivot] )
						;
				}
				else if ( Partition2 == Pivot )
				{
					Pivot = Partition1;
					while ( Partition2 > Pivot &&
							     Data[--Partition2] > Data[Pivot] )
						;
				}
				else
				{
					while ( Partition1 < Pivot &&
							     Data[++Partition1] <= Data[Pivot] )
						;
					while ( Partition2 > Pivot &&
							     Data[--Partition2] > Data[Pivot] )
						;
				}
			}
			QuickSort ( Data, Pivot );
			QuickSort ( &Data[Pivot+1], Size - 1 - Pivot );
		}
	}
}

Normally, I'd change the 'int' types in the definitions and prototypes to 'Name' (the name of the class) where necesary, but since I have to define the function to sort arrays of any type, I figured I'd make it a template function:

Code:

template <class Type>
void Swap ( Type &First, Type &Second )
{
	int Temp = First;
	First = Second;
	Second = Temp;
}

template <class Type>
void QuickSort  ( Type Data[], int Size )
{
	if ( Size > 1 )
	{
		if ( Size == 2 )
		{
			if ( Data[0] > Data[1] )
				Swap ( Data[0], Data[1] );
		}
		else
		{
			int Pivot = Size / 2, Partition1 = -1, Partition2 = Size;
			while ( Partition1 < Pivot && Data[++Partition1] <= Data[Pivot] )
				;
			while ( Partition2 > Pivot && Data[--Partition2] > Data[Pivot] )
				;
			while ( Partition1 != Pivot || Partition2 != Pivot )
			{
				swap ( Data [Partition1], Data [Partition2] );				
				if ( Partition1 == Pivot )
				{
					Pivot = Partition2;
					while ( Partition1 < Pivot &&
							     Data[++Partition1] <= Data[Pivot] )
						;
				}
				else if ( Partition2 == Pivot )
				{
					Pivot = Partition1;
					while ( Partition2 > Pivot &&
							     Data[--Partition2] > Data[Pivot] )
						;
				}
				else
				{
					while ( Partition1 < Pivot &&
							     Data[++Partition1] <= Data[Pivot] )
						;
					while ( Partition2 > Pivot &&
							     Data[--Partition2] > Data[Pivot] )
						;
				}
			}
			QuickSort ( Data, Pivot );
			QuickSort ( &Data[Pivot+1], Size - 1 - Pivot );
		}
	}
}

In doing that I got a bunch of compile error that appeared to be related to the conditional operators '<', '>', '<=', '>=', etc. Do I need to go and modify the original Name class to overload the operators?

__________________
PEBKAC = Problem Exists Between Keyboard And Chair

March 23rd, 2005, 10:37 AM

InfoGeek

Contributing User

Join Date: Mar 2005

Location: In front of my Computer

Posts: 40

Time spent in forums: 1 Day 13 h 12 m 33 sec
Reputation Power: 9

Quote:

template <class Type>
void Swap ( Type &First, Type &Second )
{
int Temp = First;
First = Second;
Second = Temp;
}

why int? it must be Type.

March 23rd, 2005, 10:42 AM

InfoGeek

Contributing User

Join Date: Mar 2005

Location: In front of my Computer

Posts: 40

Time spent in forums: 1 Day 13 h 12 m 33 sec
Reputation Power: 9

Quote:

Do I need to go and modify the original Name class to overload the operators?

Well yes, the operators you use in the quicksort template must be defined for the types you're passing to that template function.

March 23rd, 2005, 11:18 AM

Voelcker

Contributing User

Join Date: Sep 2004

Location: Maryland

Posts: 225

Time spent in forums: 1 Day 21 h 51 m 59 sec
Reputation Power: 9

How careless of me, I missed that, I'll change the 'int' in the Swap() function to 'Type'.

Thanks for your help... I'll give it a shot tonight and post back if necesary.

March 23rd, 2005, 08:57 PM

Voelcker

Contributing User

Join Date: Sep 2004

Location: Maryland

Posts: 225

Time spent in forums: 1 Day 21 h 51 m 59 sec
Reputation Power: 9

I used the same logic but a simpler QuickSort function, everything working like a charm! Thanks. (Oh, I did overload the additional operators.)

Quicksort array of class objects

Developer Shed Advertisers and Affiliates