# C Programming: Creating recursive quickSort function

1. Jul 12, 2012

### cubanmissile

1. The problem statement, all variables and given/known data
Function:
Code (Text):
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);

}

2. Relevant equations
None

3. 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?

2. Jul 13, 2012

### Staff: Mentor

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.

3. Jul 13, 2012

### Staff: Mentor

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 --
Code (Text):

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?

4. Jul 16, 2012

### cubanmissile

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)!

5. Jul 16, 2012

### Staff: Mentor

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.

6. Jul 17, 2012

### Staff: Mentor

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