Quicksort with Insertion Sort Cutoff compile issue

[Koinutron]

Hello,

First, this is an extension to homework. I have all the requirements completed, but I'm attempting to write a switch that will allow me to toggle between sorting on actual data structs, or on smart pointers to data structs. By themselves, they both work, but when attempting to combine them both into one with a command line argument switch, I get an undefined reference to my insertion sort function. No idea what's different about trying to do this except that maybe my template data types could be messing stuff up. I think some fresh eyes on the problem might help. Could somebody take a look and see what could be going on here? Relevant portions of the code are below, full source code is linked.

compiler babel

g++ src/sort3b.cpp -o sort
src/sort3b.cpp: In function 'void q1_sort(std::vector<Tdata, std::allocator<_CharT> >&, int, int) [with Tdata = person]':
src/sort3b.cpp:285:   instantiated from here
src/sort3b.cpp:195: error: no matching function for call to 'in_sort(std::vector<person, std::allocator<person> >&, int, int)'
src/sort3b.cpp: In function 'void q1_sort(std::vector<Tdata, std::allocator<_CharT> >&, int, int) [with Tdata = sptr<person>]':
src/sort3b.cpp:294:   instantiated from here
src/sort3b.cpp:193: error: no matching function for call to 'in_sort(std::vector<sptr<person>, std::allocator<sptr<person> > >&, int, int)'
make: *** [all] Error 1

Data vs pointer toggle

if(argv[4]){
	string str(argv[4]);
	if(str.compare("-d") == 0){
	data_t =1;
	gettimeofday(&timeStart, NULL); //start timer
	q1_sort<person>(plist, 0 ,plist.size()-1);
	gettimeofday(&timeEnd, NULL); //end timer
	}
	
	else if(str.compare("-p") == 0){
	data_t = 2;
	vector<sptr<person> > plistp;
	data2ptr(plist, plistp); //convert data to pointer
	gettimeofday(&timeStart, NULL); //start timer
	q1_sort<sptr<person> >(plistp, 0 ,plistp.size()-1);
	gettimeofday(&timeEnd, NULL); //end timer
	
	ptr2data(plist, plistp); //restore pointers to data
	}
	else
	help();
	}
	timersub (&timeEnd, &timeStart, &timeDifference );
	timing = timeDifference.tv_sec + .000001 * timeDifference.tv_usec; //set elapsed time in seconds

Relevant portion of the quicksort code with isort function calls

//Median of Three Quick Sort With i_sort Cutoff

template <typename Tdata>

void q1_sort(vector<Tdata> &A, int left, int right)
{
	if((right-left) < ISORT_CUTOFF){ 
		if(data_t == 1)
		{in_sort<person>(A, (int)left, (int)right+1);}	
		else if(data_t == 2)
		{in_sort<sptr<person> >(A, (int)left, (int)right+1);} 
	}

Insertion sort code modified for use in quicksort (added indices)

//Insertion Sort modified for cutoff in quicksort

template <typename Tdata>

void in_sort(vector<Tdata> &A, int left, int right)
{
	for(int x = left+1; x < right; x++){
		Tdata val = A[x];
		int j = x-1;
	while( j>=0 && val < A[j]){
		A[j+1] = A[j];
		j--;
	}
	A[j+1] = val;
	}
}

Like I said, this is not an actual part of the homework assignment, I'm just trying to add this switch in so that I can run timing and graphing scripts to compare the difference in sorting on pointers and data structs.

full in progress source code is here: http://s000.tinyupload.com/?file_id=09494203861716542481

Thanks in advance for your help!

[template<>]

template <typename Tdata>

void q1_sort(vector<Tdata> &A, int left, int right)
{
    if((right-left) < ISORT_CUTOFF){ 
        if(data_t == 1)
        {in_sort<Tdata>(A, (int)left, (int)right+1);}   
        else if(data_t == 2)
        {in_sort<Tdata>(A, (int)left, (int)right+1);} 
    }
    else{
    q1_sort<Tdata>(A, left, i-1);
    q1_sort<Tdata>(A, i+1, right);
    }
}

[Koinutron]

I know how to finish the quicksort code, I just can't get the isort cutoff switch to properly choose between template type <person> and < sptr<person> > Thanks though. :)

[template<>]

from within the q1_sort function, when it calls itself,

it needs to pass the typename like q1_sort<Tdata>(A, left, i-1);

(your original code has person type hardcoded in the function)

that should fix your undefined reference

[Koinutron]

Ahhh, I see what you did there. That template type declaration being changed from <person> or <sptr<person>> to <Tdata> made it all better. Thank you!!

Strange, it doesn't really make sense to me why it would have a problem with explicit data types being used. I suppose with using <Tdata> I don't really need the conditional statement or the global variable.

I really appreciate your help!