1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C Programming: Creating recursive quickSort function

  1. Jul 12, 2012 #1
    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. jcsd
  3. Jul 13, 2012 #2

    Borek

    User Avatar

    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.
     
  4. Jul 13, 2012 #3

    Mark44

    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?
     
  5. Jul 16, 2012 #4
    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)!
     
  6. Jul 16, 2012 #5

    Mark44

    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.
     
  7. Jul 17, 2012 #6

    Borek

    User Avatar

    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:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: C Programming: Creating recursive quickSort function
  1. Program in C (Replies: 1)

  2. C++ Program (Replies: 17)

  3. Recursive function (Replies: 16)

Loading...