C++

Forum

 
 
Troubleshooting quickSort

LioButtons (3)
Hello!

I'm writing a program that has two vectors of different class objects. The function I'm having trouble with reads from files into the two vectors and then is supposed to sort those vectors alphabetically using quickSort(). I constructed quickSort() as a template function so it could work for both vectors.

The inputting part of the function works, but if I include the quickSort() calls I get a 'vector subscript out of range' error.

The quickSort() call is like this:
1
2
3
4
5
6
7
8
9
 
void eventInfo::importRecords (void) 
{
    ...

    //sort vector employees
    quickSort(employees, 0, employees.size());
    //sort vector attendees
    quickSort(attendees, 0, attendees.size());
}


Then the template is:
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
 
template <typename T>
void quickSort(vector<T>& v, int left, int right)
{
    int p = (left + right) / 2;
    T pivot = v[p];

    int l = left;
    int r = right;

    while (l <= r) {
        while (v[l] < pivot) {
            ++l;
        }
        while (v[r] < pivot) {
            --r;
        }
        if (l <= r) {
            T tmp = v[l];
            v[l] = v[r];
            v[r] = tmp;
            l++;
            r--;
        }
    }

    if (left < r) {
        quickSort(v, left, r);
    }
    if (l < right) {
        quickSort(v, l, right);
    }
}


And I have a compare function in each object class like this:
1
2
3
4
 
bool operator< (const attendee& a1, const attendee& a2) 
{
    return (a1.name < a2.name);
}


I'm inexperienced enough that I'm not sure if it's a small error in my implementation or if I'm trying to get the program to do something that just plain doesn't make sense.
Last edited on
LioButtons (3)
Oops, noticed one mistake:
Changed 
1
2
3
 
while (v[r] < pivot) {
            --r;
        }

to
1
2
3
 
while (pivot < v[r]) {
            --r;
        }


Vector out of range error persists.
Ganado (6810)
Probably you have some sort of "fencepost" error, where you are letting l become greater than v.size()-1, or r become less than 0. Step through the code in a debugger and see at exactly which point one of your index variables becomes >= v.size().

Before you try to sort things like attendees, I suggest testing your program out with small int vectors.

e.g.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
// just to help print the vector for you
std::ostream& operator<<(std::ostream& os, const std::vector<int>& vec)
{
	os << "{ ";
	
	for (const auto& ele : vec)
	{
		os << ele << ' ';
	}
	
	return os << "}";
}

int main()
{
    std::vector<int> vec {1, 3, 5, 3};
    quickSort(vec, 0, 3);
	
    std::cout << vec << '\n';
}


Debug your code through this smaller example and you'll be able to see where the code starts to go down an unexpected path.
Last edited on
LioButtons (3)
Thank you for the advice, Gando!

Your code worked perfectly with the function, so I realized there must be something wrong with what I was passing to the function. It turns out it was a small error! I was passing vector.size() when I needed to be passing vector.size()-1!

Sometimes I get muddled up by size() counting from 1 while the indexes start from 0.

Everything works now!
Topic archived. No new replies allowed.