Need help with Quicksort

[blinksumgreen]

I've done the code below to try and implement Quicksort and it works... almost. It switches the positions of the last two items to be sorted.

Example: (using some randomly generated numbers)
- it seems to do this no matter how many elements are generated and sorted

20565
19169
17456
15724
11478
3465
0
41

a is an array that's given, p is a pivot, and r is the size.

void Quick_Sort (int* a, int p, int r)
{
	int q;
	if(p < r){
		q = Partition(a, p, r);
		Quick_Sort(a, p, q-1);
		Quick_Sort(a, q+1, r);
	}
} // Quick_Sort

int Partition(int* a, int p, int r)
{
	int x = a[r];
	int i = p-1;
	int temp;
	
	for(int j=p; j <= r-1; j++){

		if(a[j] <= x){
			i = i+1;
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		} // end if
	} // end for
	temp = a[i+1];
	a[i+1] = a[r];
	a[r] = temp;

	return i+1;
} // Partition

[Paul McKenzie]

Are you using a debugger to debug your code?

Regards,

Paul McKenzie

[Paul McKenzie]

In addition, provide a main() program that shows the calls to these functions and parameters passed that duplicate the problem. Secondly,

temp = a[i+1];

Can you guarantee that i+1 isn't outside the boundaries of the array?

Regards,

Paul McKenzie

[blinksumgreen]

I am using Visual Studio and its built in debugger.

I'm not necessarily working on the main portion of the program, I'm just responsible for writing the sorting algorithm using quicksort, and I'm given the listed things. And yes, I know that i+1 isn't outside the boundaries of the array.

[Lindley]

I'm presuming this is a homework problem, yes? Because in the real world, most developers would just call std::sort() and be done with it. (Or qsort() if they're using C.)

It would help us to debug the problem if you could provide a trivial main() function which calls Quick_Sort and demonstrates the problem.