Stack overflow error when using a recursive Quicksort

[mastakhan]

I'm trying to implement a class that uses both recursive Quicksort to sort an array, and also a recursive binary search to find a value within that sorted array.

My binary search works fine (I tested it after sorting the array with a simpler selection sort), it's my Quicksort that is throwing a stack overflow error. Specifically, the exception seems to be triggered at some point when my swap function is called as part of the QuickSort. I've spent hours on it but can't figure out why. Any ideas?

Below is my header file which also includes my class (note: I've not included a separate .cpp file that contains the function definitions for functions that read from the file, as those aren't related to the issue).

#ifndef BINARYSEARCH_H
#define BINARYSEARCH_H

#include <string>
#include <iostream>
#include <iomanip>
using namespace std;

//Global constant
const string infile_name = "testfile.bin";

//Function declarations
int32_t count_ints(string file_name);		//Counts number of integers in a binary file
void value_main(string file_name, int32_t *arrptr, int size);		//Reads integers from a binary file into an array	

//******************************************
//RecursiveSortandSearch class declaration *
//******************************************

/* This class accepts pointers to an array of ints, and a pointer to an int indicating the array size.
	It contains members to perform a recursive QuickSort to sort the array, and to perform a recursive BinarySearch
	to find a given value in the array 
	
	IMPT NOTE: to retain modularity, this class does not handle memory mangement for any pointers passed to it, and as a result
		does not contain a destructor to delete dynamic memory; if dynamic memory is allocated outside of this class and pointers to
		that memory are passed to this class's objects, it's incumbent on functions outside of the class that allocated dynamic memory 
		to manage that memory after it has been used */

class RecursiveSortandSearch {
	private:
		int *arrptr;		//Pointer to an array of ints
		int *sizeptr;		//Pointer to an int specifying the size of the array
		int search_cntr;	//Determines the number of times the binary search recurses to find a given value

		//****************************************************************************
		//Private function to partition a sublist as part of the QuickSort algorithm *
		//****************************************************************************

		int partition(int lo, int hi) {
			int pivotValue, pivotIndex, mid;

			mid = (lo + hi) / 2;
			swap(arrptr[lo], arrptr[mid]);
			pivotIndex = lo;
			pivotValue = arrptr[lo];

			for (int scan = lo + 1; scan <= hi; scan++) {
				if (arrptr[scan] < pivotValue) {
					pivotIndex++;
					swap(arrptr[pivotIndex], arrptr[scan]);
				}
			}
			swap(arrptr[lo], arrptr[pivotIndex]);
			return pivotIndex;
		}

		//******************************************************************************
		//Private function swap two values in array as part of the QuickSort algorithm *
		//******************************************************************************

//THIS SEEMS TO CAUSE THE STACK OVERFLOW WHEN CALLED AS PART OF MY QUICKSORT
		void swap(int &val1, int &val2) {
			int temp = val1;
			val1 = val2;
			val2 = temp;
		}

	public:

		//************************************************************
		//Default constructor to set arrptr to nullptr and size to 0 *
		//************************************************************
		RecursiveSortandSearch() {
			arrptr = nullptr;
			sizeptr = nullptr;
		};

		//*********************************************************************
		//Parameterized constructor to set arrptr and sizeptr to given arguments *
		//*********************************************************************
		RecursiveSortandSearch(int *aptr, int *sptr) {
			arrptr = aptr;
			sizeptr = sptr;
		}


		//*****************************************************
		//Function to sort an array using recursive QuickSort *
		//*****************************************************
		/*	Base case: low index and high index are the same
			Recursion case: low index is less than high index	*/

		void QuickSort(int lo, int hi) {
			int pivotPoint;

			if (lo < hi) {
				pivotPoint = partition(lo, hi);
				
				//Sort sublist before the pivot
				QuickSort(lo, pivotPoint - 1);
				//Sort sublist after the pivot
				QuickSort(pivotPoint + 1, hi);
			}
		}

		//********************************************************************************
		//Function to search recursively on a sorted array using binary search algorithm *
		//********************************************************************************

			/*	Base case: targetValue matches the middle value being searched
			Base case: all values have been searched, ie (start subscript + end subscript) / 2 equals either start subscript or end subscript
			Recursion case: targetValue is greater than the middle value being searched (search upper part of array)
			Recursion case: targetValue is less than the middle value being searched (search lower part of array) */

		void BinarySearch(int start_index, int end_index, int targetValue) {

			int middle = (start_index + end_index) / 2;		//Integer division is desired to maintain whole numbers

			//Base case: all values have been searched and no match, ie (start subscript + end subscript) / 2 equals either start subscript or end subscript
			if (arrptr[middle] != targetValue && (middle == start_index || middle == end_index)) {
				cout << search_cntr << ":-" << endl;
				search_cntr = 0;	//Reset search counter back to 0
				return;
			}
			//Base case: targetValue matches the middle value being searched
			else if (arrptr[middle] == targetValue) {
				cout << search_cntr << ":" << targetValue << endl;
				search_cntr = 0;
				return;
			}
			//Recursion case: targetValue is greater than the middle value being searched(search upper part of array)
			else if (arrptr[middle] < targetValue) {
				start_index = middle + 1;	//Element after middle becomes new start point in level of recursion
										
				search_cntr++;
				BinarySearch(start_index, end_index, targetValue);
			}
			//Recursion case: targetValue is less than the middle value being searched(search lower part of array)
			else if (arrptr[middle] > targetValue) {
				end_index = middle - 1;		//Element before middle becomes new end point in next level of recursion
										
				search_cntr++;
				BinarySearch(start_index, end_index, targetValue);
			}
		}

		//************************************************
		//TEST function to display contents of the array *
		//************************************************

		void display_array()
		{
			for (int row_num = 0; row_num < *sizeptr; row_num++)
			{
				//Display both the element value and eleement subscript, using formatting from <iomanip> library
				cout << setw(14) << arrptr[row_num] << "(" << row_num << ")";

				//Display only 5 elements per line
				if (row_num != 0 && (row_num + 1) % 5 == 0)
					cout << endl;
			}
		}
};

#endif 

[mastakhan]

And the main function....

#include "BinarySearch.h"
#include <string>
#include <iostream>
using namespace std;

int main()
{
	string repeat;		//String to hold user's decision to repeat program
	int32_t targetValue;		//Holds value to be searched for in array
	int32_t *sizeptr = new int32_t; //Pointer to an int to hold size of array determined at runtime

	//Determine number of integers in file and assign value via dereferenced pointer
	*sizeptr = count_ints(infile_name);		

	////TESTCOUT
	cout << "Value of sizeptr is " << *sizeptr << endl;

	int32_t *arrptr = new int32_t[*sizeptr];	//Allocate dynamic array based on number of ints in file
	value_main(infile_name, arrptr, *sizeptr);	//Read values from file into array

	//Create class object with parameterized constructor to point to the array and the array size
	RecursiveSortandSearch obj(arrptr, sizeptr);

	//Sort array in ascending order
	obj.QuickSort(0, *sizeptr - 1);   //THIS THROWS THE EXCEPTION

	////TESTCOUT - Display sorted array
	cout << endl << "Now displaying SORTED array" << endl;
	obj.display_array();
	
	//Loop to repeat searches on sorted array
	do {
		//Obtain value to search for
		cout << "Enter a value to search for: ";
		cin >> targetValue;

			//Validate user's input
			while (cin.fail()) {
				cin.clear();	//Repair instream
				cin.ignore(numeric_limits<int>::max(), '\n');	//Clear keyboard buffer
				cout << "Please enter a valid integer number" << endl;
				cin >> targetValue;
			}

		//Perform recursive binary search on sorted array
		obj.BinarySearch(0, *sizeptr - 1, targetValue);

		//Ask user if they'd like to repeat
		cout << "Go again? (y/n): ";
		cin.ignore();
		getline(cin, repeat);		

		while (repeat == ""
			|| repeat.length() != 1
			|| (toupper(repeat.front()) != 'Y' && toupper(repeat.front()) != 'N'))
		{
			//Prompt user for new input
			cout << "Please enter y or n to indicate if you'd like to go again: ";
			getline(cin, repeat);
		}
	} while (toupper(repeat.front()) == 'Y');	//Repeat program if repeat is Y or y

	//Manage dynamic memory
	delete sizeptr;
	sizeptr = nullptr;
	delete[] arrptr;
	arrptr = nullptr;

	return 0;
}

[mastakhan]

Bump - help please? Still can't figure this out.

[gunnerfunner]

perhaps someone will help you this time around but in general you, and other OP's, do need to put a bit more effort in framing your queries. dump of 225+ lines of code hoping someone will go through all of it for you .... well
let me end by a quote from stroustrup:

I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.

[lastchance]

@mastakhan

It is difficult without completely compileable code. I replaced the (non-supplied) count_ints() and value_main() with some hard-coded values and the quicksort actually worked ... but the binary search didn't.

Can you provide us with the remaining functions so that we can compile your full code, and also a (small) dataset that it fails with.

[mastakhan]

@gunnerfunner Fair feedback. I did put in a lot of effort to reduce the problem (and ended up posting ~230 lines of code vs. 600). But I see where I could have taken that further (probably reduced my main function more, or even built a smaller program that I could post instead, which as you point out is a good debugging method).

So proving that idea (and a good lesson learned), my original program that generates a stack overflow is working with a .bin file of over 125,000 integers. When I substitute another smaller file of 650 integers, with no other changes to my program whatsoever, my sort works fine (@lastchance, you're correct, I had a bug in my binary search that I wasn't aware of, I've fixed it).

I'm suspecting the stack overflow is related to the size of the file. I know that when you call functions, they take up memory in the stack; is it possible that my QuickSort is generating so may recursive function calls with the larger array size, that it's just running out of stack memory? If so, is there a way around this? I know how to allocate heap memory for variables/arrays, but is there a way to do this for function calls?

[Enoizat]

Just a secondary point:
is it possible that your private member int *sizeptr; is used just once in RecursiveSortandSearch::display_array() just to indicate the upper limit of a for-loop?
What about turning it into a simple 'int' instead of a 'int*'?

Isn't its pointed value obtained by (the non provided) int32_t count_ints(string file_name); ?

So, do you allocate dynamic memory
int32_t *sizeptr = new int32_t;
to holds an int which is returned by a function which returns 'plain' int (non pointer to)?

Well, sorry, of course is not a problem, but I'd like to understand what's the advantage compared to managing simple ints all the time.

[AbstractionAnon]

Line 61: The problem is not your swap function, per se. Your swap function is fine. You just may have been trying to call the swap function when you ran out of stack.

Line 47: This line look suspicious. Assuming hi is the index to the uppermost entry, the <= is incorrect. Array indexes range from 0 to N-1.

is it possible that my QuickSort is generating so may recursive function calls with the larger array size, that it's just running out of stack memory?

Yes. Have you tried running your program with a smaller input file?

I know how to allocate heap memory for variables/arrays, but is there a way to do this for function calls?

No. You can increase the number of stack frames you can push on the stack by reducing the number of arguments passed to the recursive function. That doesn't appear to be an option in your case. Some OS's provide a mechanism to increase the size of the stack allocated through linker options.

[lastchance]

Line 47 looked suspicious to me too. However, lines 25 and 46 in main seem to deal with it.

Is it possible there is something corrupt in your input file? Could you try just hard-coding 200000 integers in reverse order (using a loop!) and bypass your file input.

[mastakhan]

@Enoziat:

is it possible that your private member int *sizeptr; is used just once in RecursiveSortandSearch::display_array() just to indicate the upper limit of a for-loop?
What about turning it into a simple 'int' instead of a 'int*'?

Fair point, good suggestion. Probably simpler to work with the int value directly rather than the pointer.

@AbstractionAnon

Line 47: This line look suspicious. Assuming hi is the index to the uppermost entry, the <= is incorrect. Array indexes range from 0 to N-1.

You're right to do a double take on a possible off by one error, but I don't think it's an issue. The hi value passed into the QuickSort function (which then passes it into partition() ) begins as *sizeptr - 1 (line 25 in main), so N-1 is the starting value for hi.

I know how to allocate heap memory for variables/arrays, but is there a way to do this for function calls?

No.

So is there any other workaround for this, other than get a computer with more memory :)? I'd hate to think I just can't do a recursive quick sort on a 500kb file, period.

[lastchance]

If you can mark your pivot positions at each depth of the algorithm then you might just about be able to run your algorithm non-recursively ... although that does seem to take away a key element of quicksort.

P=pivot
After first partition:
------------------P-----------------

After second set of partitions
-------P----------P--------P--------

After third set of partitions
---P---P-----P----P----P---P----P---

etc.

Keep looping, dealing with all partitions of length >= 2 until no gaps between pivots of more than one item.

[Enoizat]

I'm suspecting the stack overflow is related to the size of the file.

Maybe you could solve that dilemma quite easily by a new program.

If you tried to use a std::array
http://en.cppreference.com/w/cpp/container/array
and the swap() method which cames with it, plus the std::sort() method from the <algorithm> library,
http://en.cppreference.com/w/cpp/algorithm/sort
you should be able to determine if that's the problem.

What I mean is that we can be reasonably sure that all those methods and containers are pretty optimized, and they throw meaningful exceptions too. So, if they face a stack overflow, it's quite easy to recognize it.
I think you could reuse a big part of your code, but perhaps you would need just a few lines to verify if the new one reproduces your error or not.

[TheIdeasMan]

Enoizat wrote:

So, if they face a stack overflow, it's quite easy to recognize it.

The STL containers put their data on the heap, but they could still exhaust that and throw an exception to say so. But that would require a lot of data.

@mastakhan

Although you mention the base case for the quicksort in your comments, I don't see where you implemented it in the code.

[lastchance]

Although you mention the base case for the quicksort in your comments, I don't see where you implemented it in the code.

It's the (implicit) do-nothing case opposing line 96 of the first code. Nothing to do unless lo is strictly less than hi.

Trial and error shows that on my computer the recursion blows the stack at just over 125000 integers.

@mastakhan, I think you would reduce the recursion and gain more room on the stack by not calling the base-case routines at all. Change lines 99-102 to

				//Sort sublist before the pivot
				if ( lo < pivotPoint - 1) QuickSort(lo, pivotPoint - 1);
				//Sort sublist after the pivot
				if (pivotPoint + 1 < hi) QuickSort(pivotPoint + 1, hi);