I have been writing some quicksort code and testing it on integers and all seems to be going well. Now I'm trying to use my code to read in words from a file and quicksort them. I tried using my quicksort on an array of strings but that did not work and I don't really know where to start to get it to work for strings. The following is my code so far.

#include <iostream>    // For NULL
#include "time.h"
using namespace std; 

int pickPivot = 0;
int comparisons = 0;



	//quicksort
	template< typename Type >
	void quickSort1( Type* array, int low, int high)
	{
		int pivotPosition = 0;
		int length = high;

		if (length < 11)
		{
			insertionSort (array, length);
		}

		else
		{
			if (low < high)
			{
				switch (pickPivot)
				{
				case 1:
					pivotPosition = median(array, low, high);
					break;
				case 2:
					pivotPosition = random(array, low, high);
					break;
				case 3:
					pivotPosition =partition(array, low, high);
					break;
				case 4:
					pivotPosition = medianOfnine(array, low, high);
					break;
				default:
					break;
				}
				quickSort1(array, low, pivotPosition-1);
				quickSort1(array, pivotPosition+1, high);
			}
		}
	}


	//insertion sort
	template< typename Type >
	void insertionSort( Type* array, int length)
	{
		for (int i = 1; i<length; i++)
			if (array[i]<array[i - 1])
			{
				Type temp = array[i];
				int location = i;

				do
				{
					array[location] = array[location - 1];
					location--;
				}
				while (location > 0 && array[location - 1] > temp);

				array[location] = temp;
			}
	}


	//medain as pivot
	template< typename Type >
	const Type &median( Type* array, int low, int high )
	{
		int middle = (low+high)/2;

		if ( array[low] > array[middle] )
			swap( array[middle], array[low] );
		if ( array[low] > array[high] )
			swap( array[low], array[high] );
		if ( array[middle] > array[high] )
			swap( array[high], array[middle] );

		swap(array[middle], array[low]);

		return partition(array, low, high);	
	}



	//random pivot
	template< typename Type >
	const Type &random (Type* array, int low, int high)
	{
		srand(time(NULL));
		array[low] = low+(rand()%(high-low));

		return partition (array, low, high);
	}


	//median of nine
	template< typename Type >
	const Type &medianOfnine (Type* array, int low, int high)
	{
		high = low + 9;

		return median(array, low, high);

	
	}

	//partition
	//also first elm as pivot
	template< typename Type >
	const Type &partition( Type* array, int low, int high )
	{
		int left, right;
		Type pivot;

		left = low;
		right = high;
		pivot = array[low];

		while ( left < right )
		{
			while ( array > pivot )
				right--;
			comparisons++;

			while ( (left < right) && (array <= pivot) )
				left++;
			comparisons++;

			if ( left < right )
				swap(array, array );
			comparisons++;
		}

		array[low] = array;
		array = pivot;

		return right;
	}

This is what I tried unsuccessfully in main:

#include "Quicksort.h"
#include <string>
#include <fstream>

using namespace std;

int main()
{
	string array[10];

	ifstream fin;
	fin.open("sample.txt");
	if (!fin)
	{
		cerr<<"File could not be opened"<<endl;
		exit(1);
	}

	for (int i = 0; !fin.eof(); i++)
	{
		fin>>array[i];
	}

	for(int i=0; i<10; i++)
	{
		cout <<array[i] <<endl;
	}

	pickPivot = 1;
	quickSort1(array, 1, 10);
}

Does anyone have any suggestions?

For starters, the partition function seems to be missing a lot of array indexes

I don't understand, can you be more specific?

Think a little:
1. Look at the partition returned type: must be const Type& or int ???

template< typename Type >
const Type &partition( Type* array, int low, int high )
{
int left, right;
  ...
return right; // integer value returned, not const Type& !!!
}

Look at another functions of this family. Where were your eyes? ;)
2. You have lots of function templates. No template function calls in your program. Why?

int pivotPosition = 0; // int - but all function return const Type& ???
...
pivotPosition = median(array, low, high); // median<Type>(... !!!
...
pivotPosition =partition(array, low, high); // partition<Type>(... !!!
// and so on...

3. Suppose you want to sort array[9]. What happens after

high = low + 9;
...

?
Correct these disgraceful things then come back ;)...

Ok, so I think I fixed everything that ArkM mentioned. Everything again works good for integers, but is still not working for strings and I'm getting different errors than before. Here is my changed code:

#include <iostream>    // For NULL
#include "time.h"
#include <string>

using namespace std; 

int pickPivot = 0; //Picks which pivot you want to use
int comparisons = 0;


template< typename Type >
	void quickSort1( Type* array, int low, int high)
	{
		Type pivotPosition = 0;
		int length = high;

		if (length < 11)	//If the array is less than 10 then just use insertion sort
		{
			insertionSort (array, length);
		}

		else
		{
			if (low < high)
			{
				switch (pickPivot)	//Switch used to determine which type of pivot you wan to use
				{
				case 1:
					pivotPosition = middleElm<Type>(array, low, high);
					break;
				case 2:
					pivotPosition = random<Type>(array, low, high);
					break;
				case 3:
					pivotPosition =partition<Type>(array, low, high);
					break;
				case 4:
					pivotPosition = medianOfnine<Type>(array, low, high);
					break;
				default:
					break;
				}
				quickSort1(array, low, pivotPosition-1);
				quickSort1(array, pivotPosition+1, high);
			}
		}
	}



	//Insertion sort, for use if array contains less than 10 items
	template< typename Type >
	void insertionSort( Type* array, int length)
	{
		for (int i = 1; i<length; i++)
			if (array[i]<array[i - 1])
			{
				Type temp = array[i];
				int location = i;

				do
				{
					array[location] = array[location - 1];
					location--;
				}
				while (location > 0 && array[location - 1] > temp);

				array[location] = temp;
			}
	}


	//Medain as pivot
	template< typename Type >
	const Type &middleElm( Type* array, int low, int high )
	{
		int middle = (low+high)/2;

		if ( array[low] > array[middle] )
			swap( array[middle], array[low] );
		if ( array[low] > array[high] )
			swap( array[low], array[high] );
		if ( array[middle] > array[high] )
			swap( array[high], array[middle] );

		swap(array[middle], array[low]);

		return partition<Type>(array, low, high);	
	}



	//Random  as pivot
	template< typename Type >
	const Type &random (Type* array, int low, int high)
	{
		srand(time(NULL));
		array[low] = low+(rand()%(high-low));

		return partition<Type>(array, low, high);
	}


	//Median of nine
	template< typename Type >
	const Type &medianOfnine (Type* array, int low, int high)
	{
		insertionSort(array, 9); //Does an insertion sort on the first nine elements
		high = low + 9;	//Changes high to low+9 
		int middle = (low+high)/2; //Find the middle between low(1) and high(9)

		return middle;	//Returns middle

	}

	

	template< typename Type >
	const Type &partition( Type* array, int low, int high )
	{
		int left, right;
		Type pivot;

		left = low;
		right = high;
		pivot = array[low];

		while ( left < right )
		{
			while ( array > pivot )
				right--;
			comparisons++;

			while ( (left < right) && (array <= pivot) )
				left++;
			comparisons++;

			if ( left < right )
				swap(array, array );
			comparisons++;
		}

		array[low] = array;
		array = pivot;

		return array;
	}

Here are the MANY errors:

c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(43) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::string'
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2238) : see declaration of 'std::operator -'
1> c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\driver.cpp(30) : see reference to function template instantiation 'void quickSort1<std::string>(Type *,int,int)' being compiled
1> with
1> [
1> Type=std::string
1> ]
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(43) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::string'
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2238) : see declaration of 'std::operator -'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(43) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::string'
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2238) : see declaration of 'std::operator -'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(43) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::string'
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2238) : see declaration of 'std::operator -'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(43) : error C2784: '_Base1::difference_type std::operator -(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::string'
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2039) : see declaration of 'std::operator -'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(43) : error C2784: '_Base1::difference_type std::operator -(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::string'
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2039) : see declaration of 'std::operator -'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(43) : error C2784: '_Base1::difference_type std::operator -(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::string'
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2039) : see declaration of 'std::operator -'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(43) : error C2784: '_Base1::difference_type std::operator -(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::string'
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2039) : see declaration of 'std::operator -'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(43) : error C2676: binary '-' : 'std::string' does not define this operator or a conversion to a type acceptable to the predefined operator
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(44) : error C2782: 'std::basic_string<_Elem,_Traits,_Alloc> std::operator +(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem)' : template parameter '_Elem' is ambiguous
1> c:\program files\microsoft visual studio 9.0\vc\include\string(60) : see declaration of 'std::operator +'
1> could be 'int'
1> or 'char'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(44) : error C2784: 'std::basic_string<_Elem,_Traits,_Alloc> std::operator +(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : could not deduce template argument for 'const _Elem *' from 'int'
1> c:\program files\microsoft visual studio 9.0\vc\include\string(50) : see declaration of 'std::operator +'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(44) : error C2784: 'std::basic_string<_Elem,_Traits,_Alloc> std::operator +(const _Elem,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'int'
1> c:\program files\microsoft visual studio 9.0\vc\include\string(40) : see declaration of 'std::operator +'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(44) : error C2784: 'std::basic_string<_Elem,_Traits,_Alloc> std::operator +(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const _Elem *' from 'std::string'
1> c:\program files\microsoft visual studio 9.0\vc\include\string(30) : see declaration of 'std::operator +'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(44) : error C2784: 'std::basic_string<_Elem,_Traits,_Alloc> std::operator +(const std::basic_string<_Elem,_Traits,_Alloc> &,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'int'
1> c:\program files\microsoft visual studio 9.0\vc\include\string(20) : see declaration of 'std::operator +'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(44) : error C2784: 'std::_String_iterator<_Elem,_Traits,_Alloc> std::operator +(_String_iterator<_Elem,_Traits,_Alloc>::difference_type,std::_String_iterator<_Elem,_Traits,_Alloc>)' : could not deduce template argument for 'std::_String_iterator<_Elem,_Traits,_Alloc>' from 'int'
1> c:\program files\microsoft visual studio 9.0\vc\include\xstring(440) : see declaration of 'std::operator +'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(44) : error C2784: 'std::_String_const_iterator<_Elem,_Traits,_Alloc> std::operator +(_String_const_iterator<_Elem,_Traits,_Alloc>::difference_type,std::_String_const_iterator<_Elem,_Traits,_Alloc>)' : could not deduce template argument for 'std::_String_const_iterator<_Elem,_Traits,_Alloc>' from 'int'
1> c:\program files\microsoft visual studio 9.0\vc\include\xstring(300) : see declaration of 'std::operator +'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(44) : error C2784: 'std::reverse_iterator<_RanIt> std::operator +(_Diff,const std::reverse_iterator<_RanIt> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'int'
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2229) : see declaration of 'std::operator +'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(44) : error C2784: 'std::_Revranit<_RanIt,_Base> std::operator +(_Diff,const std::_Revranit<_RanIt,_Base> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'int'
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2029) : see declaration of 'std::operator +'
1>c:\users\tracy\documents\visual studio 2008\projects\project 4\project 4\quicksort.h(44) : error C2676: binary '+' : 'std::string' does not define this operator or a conversion to a type acceptable to the predefined operator

I have no idea what these errors mean, can anyone explain?

Come back to the vmanes's post. In the function partition you compare an array with its element, assign an array to an element, return an array instead of value - and so on. Totally incorrect code. In random you call srand - why? You need srand call once in main only. The medianOfnine (again: what happens if no 9 elements in an array? ) returns a reference (why reference? ) to local variable.
You never used this code to sort integers. You can't compile it for any template argument.

Two things:

1.)Ok, if I run my program with less than 10 items it does an insertion sort. When it does this I get some really weird output that looks like this:

Unsorted:
the
those
have
tplus
the
joker
happy
apple
in

Variation 1 Median
======================
Total # of comparison : 0 Average # of comparisons : 0
apple
happy
have
in
joker
the
those
tplus
(²0 ∞`☺☺☺ 8²0 X6☺☺☺ ‼♠ Φ!♠ /╘═' ≡²⌂dz┌ 1 ⁿⁿ0 ☻ |²0 »►
☺☺W╖ⁿ& @²0 ƒ4☺☺L²0 ◄I▬w ≡²⌂î²0 ╢Σîw ≡²⌂ÉÆ»w ≡²⌂ X²0
4ÿëwΣP► ñ²0 ëΣîw╟◄☺☺ ≡²⌂ ╟◄☺☺ ≡²⌂

Press any key to continue . . .

I have never seen this before and have no idea what it could be. Does anyone know?

Here is my revised code if it helps:

#include <iostream>    // For NULL
#include "time.h"
#include <string>

using namespace std; 

int pickPivot = 0; //Picks which pivot you want to use
int comparisons = 0;


template< typename Type >
	void quickSort1( Type list[] , int low, int high)
	{
		int pivotPosition = 0;
		int length = high;

		if (length < 11)	//If the array is less than 10 then just use insertion sort
		{
			insertionSort (list, length);
		}

		else
		{
			if (low < high)
			{
				switch (pickPivot)	//Switch used to determine which type of pivot you wan to use
				{
				case 1:
					pivotPosition = middleElm(list, low, high);
					break;
				case 2:
					pivotPosition = random(list, low, high);
					break;
				case 3:
					pivotPosition =partition(list, low, high);
					break;
				case 4:
					pivotPosition = medianOfnine(list, low, high);
					break;
				default:
					break;
				}
				quickSort1(list, low, pivotPosition-1);
				quickSort1(list, pivotPosition+1, high);
			}
		}
	}



	//Insertion sort, for use if array contains less than 10 items
	template< typename Type >
	void insertionSort( Type list[], int length)
	{
		for (int i = 1; i<length; i++)
			if (list[i]<list[i - 1])
			{
				Type temp = list[i];
				int location = i;

				do
				{
					list[location] = list[location - 1];
					location--;
				}
				while (location > 0 && list[location - 1] > temp);

				list[location] = temp;
			}
	}


	//Medain as pivot
	template< typename Type >
	int middleElm( Type list[], int low, int high )
	{
		swap(list, low, (low+high)/2);
		return partition(list, low, high);	
	}


	template<typename Type>
	void swap (Type list[], int low, int high)
	{
		Type temp;

		temp = list[low];
		list[low] = list [high];
		list[high] = temp;
	}



	//Random  as pivot
	template< typename Type >
	int random (Type list[], int low, int high)
	{
		list[low] = low+(rand()%(high-low));
		return partition(list, low, high);
	}


	//Median of nine
	template< typename Type >
	int medianOfnine (Type list[], int low, int high)
	{
		insertionSort(list, 9); //Does an insertion sort on the first nine elements
		high = low + 9;	//Changes high to low+9 
		int middle = (low+high)/2; //Find the middle between low(1) and high(9)

		return middle;	//Returns middle

	}

	

	template< typename Type >
	int partition( Type list[], int low, int high )
	{
		int index, smallIndex;
		Type pivot;

		//swap(array, low, (low+high)/2);

		pivot = list[low];
		smallIndex = low;

		for(index = low + 1; index <= high; index++)
			if (list[index]<pivot)
			{
				smallIndex++;
				swap(list, smallIndex, index);
			}

		swap(list, low, smallIndex);

		return smallIndex;
		
	}


	//Quicksort version 2
	template< typename Type >
	void quickSort2( Type list[], int low, int high)
	{
		Type pivotPosition = 0;
		int length = high;

		if (length < 11)	//If the array is less than return, insertion done after
			return;

		else
		{
			if (low < high)
			{
				switch (pickPivot)	//Switch used to determine which type of pivot you wan to use
				{
				case 1:
					pivotPosition = median(list, low, high);
					break;
				case 2:
					pivotPosition = random(list, low, high);
					break;
				case 3:
					pivotPosition =partition(list, low, high);
					break;
				case 4:
					pivotPosition = medianOfnine(list, low, high);
					break;
				default:
					break;
				}
				quickSort1(list, low, pivotPosition-1);
				quickSort1(list, pivotPosition+1, high);
			}
		}
	}

And here's my main.cpp

#include "Quicksort.h"
#include <string>
#include <fstream>
#include <cstdlib>

using namespace std;

int main()
{

	string array[10];

	ifstream fin;
	fin.open("sample.txt");
	if (!fin)
	{
		cerr<<"File could not be opened"<<endl;
		exit(1);
	}

	for (int i = 0; !fin.eof(); i++)
	{
		fin>>array[i];
	}

	cout<<"Unsorted:"<<endl;
	for(int i=0; i<10; i++)
	{
		cout <<array[i] <<endl;
	}

	pickPivot = 1;
	quickSort1(array, 1, 10);

	cout<<"Variation 1	Median"<<endl;
	cout<<"======================"<<endl;
	cout<<"Total # of comparison : "<<comparisons<<"     Average # of comparisons : "<<comparisons<<endl;;

	for (int i =1; i<11; i++)
	{
		if (array[i] != array[i+1])
		{
			cout<<array[i]<<endl;
		}
	}


	return 0;
}

2.) If I try to run the actual quicksort with any pivot the program compiles but when ran, stops working at the quicksort. I thought I fixed alot of stuff but it's still not working. Any ideas?

You are trying to print element with index 10 and compare elements with indicies 10 and 11 from the array of 10 strings but correct indicies are 0..9:

for (int i =1; i<11; i++)
	{
		if (array[i] != array[i+1])
		{
			cout<<array[i]<<endl;
		}
	}

Of course, the program crashed when accessed inexistent std::string objects.
You don't print the 1st element array[0]...

Yet another free advice. Never, ever write such codes:

string array[10];
...
for (int i = 0; !fin.eof(); i++)
{
    fin>>array[i];
}

If an input file contains more than 10 words your program crashed in unpredictable manner.

const int N = 10;
...
string array[N];
int n;
...
for (n = 0; n < N && (cin >> array[n]); ++n)
    ;
// Now n is a real number of initialized elements.

Getting closer:) This quicksort now works for the middle element as the pivot, and to first element as the pivot. I am still having a problem with a random element as the pivot and the median of the first nine elements as the pivot.

The function for random pivot:

template< typename Type >
	int random (Type list[], int low, int high)
	{
		low = (rand()%(high-low));
		return partition(list, low, high);
	}

When I try this method I get funny symbols again for the output


The function for median of nine:

//Median of nine
	template< typename Type >
	int medianOfnine (Type list[], int low, int high)
	{


		insertionSort(list, 8); //Does an insertion sort on the first nine elements
		high = 8;	//Changes high to 9, range is now 0-8 
		int middle = (low+high)/2; //Find the middle between low(1) and high(8)

		return middle;	//Returns middle as pivot point

	}

This one crashes when compiled

Better correct known defects.
It seems you are an extraordinary brave person: you never test index boundaries, assign arbitrary indicies and go forward although there are a lots of errors in the rear ;)

Probably David Glasgow Farragut is your Hero:

Damn the torpedoes, full speed ahead!

He won. And you?..

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.