C Programming: Creating recursive quickSort function

[cubanmissile]

Homework Statement

Function:

void quickSort(struct student *array, int start, int end) {

	int i = start;
	int j = end;

	while(i < j) {

		// Move left counter, then right counter.
		while(i <= end && array[i].numDays <= array[start].numDays)
			i++;

		while(array[j].numDays > array[start].numDays)
			j--;

		if(i < j)
			swap(array, i, j);

	}

	swap(array, start, j);

	if(array[j].numDays < array[start].numDays)
		quickSort(array, 0, j);
	if(array[j].numDays > array[end].numDays)
		quickSort(array, j, end);

}

Homework Equations

None

The Attempt at a Solution

I have tried many different versions. Changing the variables from array[j] to array > array[start], as well as changing the bottom statement. This doesn't correctly sort the array however... Is there something I am missing? Look at this, I would *assume* it would work.

Here's why:

First, it increases the left index...then the right. Once all that's done and the elements are swapped, it checks to see if the element on the right index is larger than the element at the left index. If so, run quickSort again. Then after that recursive call, it then checks to the right of the partition element. If it's larger than the end element, recursively call until it is not.

So, why would it not be working?

 

[Borek]

Use debugger or add a call to a function that will display the content of the sorted table, this way you will see for yourself what is happening and where the function does something different than you think it does.

 

[Mark44]

A couple of things that come to mind:
1) You don't show the code for your swap function. Without seeing it, I can't tell if it's working correctly.

2) In this code --

if(array[j].numDays < array[start].numDays)
   quickSort(array, 0, j);
if(array[j].numDays > array[end].numDays)
   quickSort(array, j, end);

what happens if array[j].numDays == array[start].numDays?

 

[cubanmissile]

A couple of things that come to mind:
1) You don't show the code for your swap function. Without seeing it, I can't tell if it's working correctly.

2) In this code --

if(array[j].numDays < array[start].numDays)
   quickSort(array, 0, j);
if(array[j].numDays > array[end].numDays)
   quickSort(array, j, end);

what happens if array[j].numDays == array[start].numDays?

Actually, it was my sort function that was causing the quickSort to not work. :) Thank you guys very much for the help! Programming is fun (not sarcasm, I truly love programming)!

 

[Mark44]

Actually, it was my sort function that was causing the quickSort to not work. :) Thank you guys very much for the help! Programming is fun (not sarcasm, I truly love programming)!

I think so, too. It's very satisfying to write some code (that typically has a few bugs in it), and then figure out why it's not doing what you want it to do.

 

[Borek]

I think so, too. It's very satisfying to write some code (that typically has a few bugs in it), and then figure out why it's not doing what you want it to do.

And then realizing that approach you took could never, ever yield what you wanted and you have to start again. Very satisfying indeed :tongue2: