Question about quicksort

[BananaCode]

void quicksort (int* a, int l, int r)
{
	int temp, left=l, right=r;
	if (r-l<1)
	{
		return;
	}
	int pivot = rand() % right+1;
	temp = a[pivot];		//Put the pivot at the end of the array
	a[pivot] = a[right];
	a[right] = temp;
	pivot = a[right];
	right--;				//Move the pointer so that the pivot is "outside" of the array
	
	while (left<right && !(a[left] == a[right]))
	{

		for (;a[left] < pivot;left++)
		{
		}
		for (;a[right] > pivot;right--)
		{
		}
		if (left<right)
		{
			temp = a[left];
			a[left] = a[right];
			a[right] = temp;
		}
	}
	temp = a[left]; //left will have the proper position of the pivot. Switch the pivot element with the element "left"
	a[left] = a[r];
	a[r] = temp;
	quicksort(a,l,left-1);
	quicksort(a,left+1,r);

}

I understood now your points and implemented what you said. The algorithm sometimes sorts correctly, sometimes not. This has to do with the pivot element. Fun2code has pointed out that the random selection isn't correct. Can you see the error?

[ne555]

http://www.cplusplus.com/forum/beginner/42742/#msg233745

fun2code wrote:

pivot must be between left and right not 1 and right

while (left<right 
    && !(a[left] == a[right])) //this condition makes no sense (think in repeated values) 

Also if you allow repeated values

		for (;a[left] < pivot;left++) //suppose a[left] == pivot
		{
		}
		for (;a[right] > pivot;right--) //suppose a[right] == pivot
		{
		}
		if (left<right) //true
		{
			temp = a[left];
			a[left] = a[right];
			a[right] = temp;
		}

the next iteration the index left and right will not move -> infinite loop.
An easy way to fix it is to adjust them after the swap.

You need to check for out of bounds too.

[BananaCode]

How do I select a random value between two values?

New code to counter the infinite loop and removed the condition that made no sense (I originally put that in in case of a[right] == a[left] == pivot)

while (left<right)
	{
		for (;a[left] < pivot;left++)
		{
		}
		for (;a[right] > pivot;right--)
		{
		}
		if (left<right)
		{
			temp = a[left];
			a[left] = a[right];
			a[right] = temp;
			right--;
			left++;
		}
	}

[D80DSL3A]

You can get a value at random between left and right (inclusive) with this:
int pivot = left + rand()%(right-left);
Of course, right-left must be > 0.

ne555 is doing a fine job of helping you with the logic so I won't try to do that.
Please compare your logic to working code.

void quicksort(int A[], int left, int right)
{
	if(right > left)
	{
		int pivotIdx = left + rand()%(right-left);// any value left <= pivotIdx <= right is OK here
		int newPivotIdx = partition(A,left,right,pivotIdx);
		quicksort(A,left,newPivotIdx-1);
		quicksort(A,newPivotIdx+1,right);
	}
	return;
}

1) A pivot index is chosen, here at random (an unnecessary complication?).
2) a new pivot index is returned by the partition function, which places all values <= the pivot value on the left side of the array.
3) The array is split at the new pivot location and the 2 portions are treated as above.
Here is the partition function:

int partition(int A[], int left, int right, int pivotIdx)
{
	int pivotVal = A[pivotIdx];// value at given pivot location
	swap(A,pivotIdx,right);// place the pivot value at the right end of the array
	int stIdx = left;// store index: low values get moved to the left end of the array.

	for(int i=left; i<right; ++i)// look through the array for low values to move to the left
		if(A[i] <= pivotVal)		
			swap(A,i,stIdx++);// keep stIdx just right of the low values found
		
	swap(A,stIdx,right);	// place the pivot value after the low values
	return stIdx;// stIdx is the new pivot location. Values <= are to the left and values > are to the right
}

The swap() is trivial:

void swap(int A[], int i, int j)
{
	if(i==j)// don't bother swapping
		return;
	int temp = A[i];
	A[i] = A[j];
	A[j] = temp;
	return;
}