why SIGSEGV runtime error?

help
, ,
1

Could someone please tell me why this is giving me a runtime error (SIGSEGV). I tried to implement my own quicksort rather than the C++ standard sort for the problem, but it ends up giving the runtime error. When I use the C++ sort, it doesn’t return an error, so the problem has to be in my version of the sort.

The link to my full solution is here: http://www.codechef.com/users/shanman17

The problem is here: http://www.codechef.com/problems/BUYING2

Here’s my code for the sort:

vector<int> concat(vector<int> low, vector<int> high){
	low.insert(low.end(), high.begin(), high.end());
	return low;
}

vector<int> quicksort(vector<int> array){
	int size = array.size(), pivot = (array[0] + array[size - 1]) / 2;
	if (size > 1){
		vector<int> low;
		vector<int> high;
		for (int a = 0; a < size; a++){
			if (array[a] <= pivot){
				low.push_back(array[a]);
			}
			else if (array[a] > pivot){
				high.push_back(array[a]);
			}
		}
		return concat(quicksort(low), quicksort(high));
	}
	else {
		return array;
	}
}
2

I can give you a case for segmentation error.

When size is 2 and say both elements go into low vector. Consequently size of high vector is 0. As a result low vector will always recurse with same situation and infinite loop occurs.

In general, if pivot takes the largest or smallest value in the array, then whole array goes into either low or high vector, and recursion wont be of any use then.