0

I've seen some code in Google implementing Quicksort algorithm like this.

static public void QuickSort_Recursive(int [] arr, int left, int right)
{
    // For Recusrion
    if(left < right)
    {
        int pivot = Partition(arr, left, right);

        if(pivot > 1)
            QuickSort_Recursive(arr, left, pivot - 1);

        if(pivot + 1 < right)
            QuickSort_Recursive(arr, pivot + 1, right);
    }
}

I tried to work out with this, I've already understood how the code itself works but one thing I got confused. How the recursion (the code above) works. How it is getting terminated. I am new in recursive functions, I only know its basic.

Can someone explain it to me in a straight to the point and simple explanation. :)

P.S: I know the Partitioning parts so I didn't include it.

Improve this question
1
  • The checks for (pivot > 1) (which should be (pivot - 1 > left) and (pivot + 1 < right) aren't necessary, although they save an extra call. The check for (left < right) on the recursive call will catch both those cases, since the parameters are signed ints. Commented Jan 23, 2017 at 13:31

2 Answers 2

Reset to default
1

As you probably know, recursion works by defining the larger problem in terms of its smaller instances and solves the larger problem by solving the smaller instances of the problem and using those solutions to construct the larger solution.

In your case, the if statement that checks left < right is the answer to your question. As Quicksort_recursive recursively decreases the size of the problem, there will come a point where the array only has 1 element in it. Then, left will be equal to right, and the function will not need to continue trying to recursively solve smaller instances of the problem. The reason is simple: there are no smaller instances of the problem. In other words, there are no non-empty subarrays to sort which has a size smaller than 1.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

@rcgldr I think you misunderstood what I meant with decreasing the size. Considering your example, what you describe to be increasing as you go deeper into the recursion is the number of instances of a problem to solve. That is an issue for certain recursive problems, sure, but it is irrelevant to what I meant with decreasing size of the problem. When I said that recursion works by decreasing the size, I meant that problem f(N) is defined in terms of f(k_i) such that for all values of i k_i<N.
@rcgldr I believe all the points you are making are correct, yes. But note that in the question the emphasis is on the recursion (i.e. reducing problem size) not ordering. I think your explanation complicates things by including too much of the theory of an efficient quicksort implementation. OP clearly asks how recursion works on a specific implementation of quicksort, rather than on an efficient implementation of quicksort. That's why I based my answer on the specific code OP asked, and why my answer features the base case as 1.
It appears we have a difference in how we define the term base case. Your definition is, I think, "the smallest instance of the problem that something is done". My idea of a base case is "the smallest instance of a problem that is called via QuickSort_Recursive". (i.e. the call that stops the recursion) True, nothing is done for arrays of size <2, but that's exactly why they're the base case. In Fibonacci numbers, you don't do anything to define the base cases. They are defined alongside the problem. Similarly, in here, arrays of size 0&1 are defined to be sorted, making them the base case
Look, I get it, which is why I have said that there is a difference in how we define the base case. But nobody but you is talking about various implementations of quicksort, let alone mergesort! OP asked about a particular implementation, and I provided a specific response. Why are you insisting on providing an answer to a question that was not asked?!
The OP's specific example code has an error. It the second if was fixed to if(pivot - 1 > left), along with the third if(pivot + 1 < right), I don't see how a recursive call with a base case of 1 could occur (other than an initial call with left >= right) with the corrected example code.
0

In sequential terms, each recursive call pushes all the local variables (including the function parameters) and the current code position onto a stack (the call stack) and then jumps to the start of the function, with the new parameters. When the call finishes, it pops the variables and return address from the stack, and drops back to where the call was made.

But the best way to understand recursion is actually to not try to work it out sequentially, but in terms of breaking down the problem into parts. You sort an array by splitting it in two parts, and then sorting each of the parts – unless the parts are size 1 or 0, in case you stop and finish that part (which is trivial, less than 2 elements is always sorted) without breaking it down further.

The execution is kind of like binary tree, where the leaves are the stop condition of subarray size 0 or 1.

I suggest modifying the code like this:

static public void QuickSort_Recursive(int [] arr, int left, int right) {
    QuickSort_Recursive(arr, left, right, 1);
}

static public void QuickSort_Recursive(int [] arr, int left, int right, int depth)
{
    System.out.println(String.format("%"+(depth*3)+"sleft=%d, right=%d", "", left, right));
    // For Recusrion
    if(left < right)
        {
            int pivot = Partition(arr, left, right);

            if(pivot > 1)
                QuickSort_Recursive(arr, left, pivot - 1, depth+1);

            if(pivot + 1 < right)
                QuickSort_Recursive(arr, pivot + 1, right, depth+1);
        }
}

That will give you a printout at each call that may help you understand what's happening.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.