Quicksort Template function

optimus203 (13)
Hey everyone. I'm having problems implementing a quicksort template function, to sort a vector of class pointers.

I'm getting the following error:
error C2664: 'Qsort<T>::partition' : cannot convert parameter 1 from 'std::vector<_Ty>' to 'std::vector<_Ty> &'

Here are my code snippets. Thanks in advance for everyone's time and help.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
// Qsort.h file
#include <vector>
using namespace std;

// Quicksort class
template <typename T>
class Qsort
{
public:
	// Constructor
	Qsort();
	Qsort(vector<T*> &vec, int from, int to);

	// partition vector for quicksort
	int partition(vector<T*> &vec, int from, int to);

	// quicksort function
	// int quicksort(vector<T*> &vec, int from, int to);
};


// Constructor
template <typename T>
Qsort<T>::Qsort()
{
	//
}

// Partition
// ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
template <typename T>
int Qsort<T>::partition(vector<T*> &vec, int start, int end)
{
	int pivot = vec[end];                                      
    int bottom = start-1;                                                  
    int top = end;                                                          

    bool continue = true;
    while (continue)
    {
        while (continue)
		{
            bottom += 1;

            if (bottom == top)
			{
				continue = false;                       
                break;
			}

            if (vec[bottom] > pivot)  
			{
                vec[top] = vec[bottom];
                break;
			}
		}
		while (continue)
		{
			top = top-1;                     
		
			if (top == bottom)
			{
				continue = false;                     
				break;
			}
		
			if (vec[top] < pivot)
			{  
				vec[bottom] = vec[top];
				break;
			}     
		}
    }
    vec[top] = pivot;
    return top;
}

template <typename T>
Qsort<T>::Qsort(vector<T*> &vec, int start, int end)
{
	if (start < end)    
	{
		int split = partition(vec, start, end); 
		Qsort(vec, start, split-1);
		Qsort(vec, split+1, end);
	}
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include <iostream>
#include <algorithm>
#include <vector>
#include "appointment.h"
#include "qsort.h"
using namespace std;

int main () {
	// derived classes generated
	Derived1 app1, app2;
	Derived2 app3, app4;

	// get data from file
	app1.populate_app("==1");
	app2.populate_app("==2");
	app3.populate_app("==3");
	app4.populate_app("==4");   

	// Store in vector of pointers
	vector<Appointment_Class*> print(4);
	print[0] = &app1;
	print[1] = &app2;
	print[2] = &app3;
	print[3] = &app4;

	Qsort<Appointment*> SortedSchedule(print_apps, 0, print_apps.size()-1);

	cout << "The quick-sorted vector:\n\n";
	for(int i = 0; i < print_apps.size(); i++)
	{
		cout << print_apps[i] << endl;
	}

	system("pause");
    return 0;
}
Last edited on
Peter87 (11256)
Shouldn't Qsort(vector<Appointment*> &vec, int from, int to); be Qsort(vector<T*> &vec, int from, int to);?
optimus203 (13)
Thanks Peter. Made that revisions, and the following compile error occurs. I do have a Date and Time class setup, but I don't think that is the problem. I've also updated the source code above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
  problem2b_tester.cpp
c:\problem2b_tester.cpp(99): error C2664: 'Qsort<T>::Qsort(std::vector<_Ty> &,int,int)' : cannot convert parameter 1 from 'std::vector<_Ty>' to 'std::vector<_Ty> &'
          with
          [
              T=Appointment *,
              _Ty=Appointment **
          ]
          and
          [
              _Ty=Appointment *
          ]
          and
          [
              _Ty=Appointment **
          ]
c:\problem2b_tester.cpp(102): warning C4018: '<' : signed/unsigned mismatch
  problem2b_appointment.cpp
  Generating Code...
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

Last edited on
vlad from moscow (6539)
I think the problem is that when you are defining

Qsort<Appointment*> SortedSchedule(print_apps, 0, print_apps.size()-1);

template argument that corresponds to T is Appointment*. So the vector shall have value type of Appointment** (pointer to pointer to Appointment).
Last edited on
optimus203 (13)
Good point. That resolved that error but creating a plethora of other issues - unfortunately. Thanks for the help!
Topic archived. No new replies allowed.