Recursive Quick Sort (Brain Exploded!!)

[Triryche]

I am studying a recursive quick sort algorithm by C.A.R. Hoare. (a classic I presume).

The code appears to be working properly.
I totally get the concept of recursion,and I must say, I am having a blast trying to teach myself C++ (it is purely recreational use right now, honest!!)

I am trying to wrap my brain around the logic flow and I am a bit tripped up on the first twowhile statements:

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


void qs(char *items, int L, int R)
{
	int i , j ;
	char x , y;
	
	i= L ; j = R;
	x = items [(L+R)/2];
	do {
		while ((items[i] < x) && (i < R)) i++; // please help me with the logic flow 
		while ((x < items[j]) && (j > L)) j--; //of these two while statements 
		if(i <= j) {
		y = items[i];
		items[i] = items[j];
		items[j] = y;
		i++; j--;
		}
	} while (i <= j);

	if(L < j) qs(items, L , j);
	if(i < R) qs(items, i, R);
}

I understand the AND as it applies to its while but not how the 2 act together.
Do they behave like an AND or OR operator or ....??

[screw]

Hi!


A while loop is working until its condition is true. The condition can be compound.

while ((items[i] < x) && (i < R)) i++;

You can see two expressions which are attached with logical AND (&& symbol). These return true or false. C++ evaluate them left to right.

Firstly (items[i] < x) is examined. (if the element of the items array is less then x then return true else false)

If this condition is satisfied then the second condition is evaluated too.

So this code fragment acts the following: The elements of the array item are gone while the elements are less then the value of x variable AND the index value of i variable is less then R variable.


The quicksort algorithm:
(Modern technology :)

http://www.youtube.com/watch?v=vxENKlcs2Tw

http://en.wikipedia.org/wiki/Quicksort

[Chewbob]

A while loop is working until its condition is true.

You mean false.

[screw]

You are right. Then you would have written why not (for the topics creator).


A while loop works until its condition is true AND there isn't exception, return statement or goto, exit break aren't used in addition the operating system doesn't freeze and the computer doesn't burn down etc.

(I learned that all algorithm must have one entire point and one exit point, so more return and goto isn't recommended and he won't learn about the exceptions now)


But I think they aren't relevant informations for beginners.

[Triryche]

I understand the concept of the quick sort && I understand how each individual while statement evaluates to TRUE or FALSE.
What I am having trouble with are the TWO while statements together in lines 15,16. Do the two whiles act like an && , an || (or something else)??
Meanwhile I guess I can write a simple program to investigate.
Cool video btw!!

[yadude1e3]

The while loops are just to iterate the variables i and j. They don't affect eachother in any way.

It might make more sense to write it like this:

while ((items[i] < x) && (i < R))
{ 
    i++;
}

while ((x < items[j]) && (j > L))
{
    j--;
}

[Triryche]

Thanks!!
It clicked!!

[screw]

Sorry, I didn't understand you.. :)