0

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?

3
Contributors
10
Replies
11
Views
8 Years
Discussion Span
Last Post by ArkM
0

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 ;)...

0

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?

0

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.

0

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?

0

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]...

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.
0

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

0

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?..

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.