if criteria problem in recursive function

[Timminski]

Hi all.

I can't figure out why the last if statement in the qs function (line 74) is executing when it appears the criteria for the if isn't being met. I've added in some cout statements to see what is happening to the variables and sure enough the condition for the if isn't being met by line 72 - but as the output shows; this line is printed twice, and on the second occasion the values have changed. The program is from a tutorial and works fine; but I don't understand why it does what it does. Can anyone tell me why these values change at that particular line?

//THE QUICKSORT USING RECURSION
#include <iostream>
#include <cstring>
using namespace std;

void quicksort(char *items, int len);
void qs(char *items, int left, int right);

int main() {

	char str[] = "qwfjb";

	cout << "original order: " << str << "\n";

	quicksort(str, strlen(str));

	cout << "Sorted order: " << str << "\n";

}

//Set up a call to the actual sorting function

void quicksort(char *items, int len) {
	qs(items, 0, len-1);
}

//A recursive version of quicksort for sorting characters
void qs(char *items, int left, int right) {
	int i, j;
	char x, y;

	i = left;
	cout << "i = " << i << "\n";
	cout << "items i = " << items[i] << "\n";
	cout << "left = " << left << "\n";

	j = right;
	cout << "j = " << j << "\n";
	cout << "right = " << right << "\n";

	x = items[(left+right) / 2]; 
	cout << "x = " << x << "\n";

		do {
			while((items[i] < x) && (i < right)) { 
				i++; 
				cout << "in the while loop i = " << i << "\n";
			}

			while((x < items[j]) && (j > left)) {
				j--; 
				cout << "in the while loop j = " << j << "\n";
			}

			if(i <= j) { 
				y = items [i];
				items[i] = items[j];
				items[j] = y;
				i++; j--;
				cout << "at the end of nested if i = " << i << " and j = " << j << "\n";
			}

		} while(i <= j);

	if(left < j) {
		cout << "doing first if\n";
		qs(items, left, j);
	}

	cout << "\n\nHERE IS THE PROBLEM\n\n\n";

	cout << "i = " << i << " right = " << right << "\n";

	if(i < right) {
		cout << "doing second if\n";
		qs(items, i, right);
	}

}

Here is the output as far as the problem:

original order: qwfjb
i = 0
items i = q
left = 0
j = 4
right = 4
x = f
at the end of nested if i = 1 and j = 3
in the while loop j = 2
at the end of nested if i = 2 and j = 1
doing first if
i = 0
items i = b
left = 0
j = 1
right = 1
x = b
in the while loop j = 0
at the end of nested if i = 1 and j = -1


HERE IS THE PROBLEM


i = 1 right = 1


HERE IS THE PROBLEM


i = 2 right = 4
doing second if
...

[Dacster13]

lolz, with all the cout's you placed it was a bit confusing for me. Anyways, the reason it is being called twice is because it's a recursive function so it calls itself, and after the second call to itself is done it returns back to where it stopped in your first call and starts executing from there.

so basically it's like this

main calls quicksort
quicksort calls qs
qs finds a call to itself and jumps to executing a second qs.
second qs finishes executing and goes back to the first qs call and resumes executing the
remaining statements in the first qs.

it sees the following code block and executes it as well, changing the values of your variables.

do {
			while((items[i] < x) && (i < right)) { 
				i++; 
				cout << "in the while loop i = " << i << "\n";
			}

			while((x < items[j]) && (j > left)) {
				j--; 
				cout << "in the while loop j = " << j << "\n";
			}

			if(i <= j) { 
				y = items [i];
				items[i] = items[j];
				items[j] = y;
				i++; j--;
				cout << "at the end of nested if i = " << i << " and j = " << j << "\n";
			}

		} while(i <= j);

then it checks your values in the if statement , i = 2 and right = 4 now though so it becomes true. and executes the statements inside of it.
then the first qs finishes and returns to quicksort.
quicksort finishes and returns to main
main reaches it's end and stops executing.

It probably makes more than 2 calls to itself though because it's sorting out the string. But logically that's how it's happening. Hopefully that explains it well enough. :P

[Timminski]

Thanks for taking the time to explain that Dacster - it makes sense; I mistakenly thought that after the second call to qs ran it's course it would return to quicksort and then main. But as i should have remembered; when a function is called and executed, the program resumes on the next line after the function call - which in this case would be where the first call to qs called the second.