How the recursive function terminated in Quicksort Algorithm?

Question

I tried to work on breakpoints so that I can follow how this recursive function in Quicksort Algorithm works.

    static public void SortQuick(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int pivot = Partition(arr, left, right);

            if (pivot > 1)
            {
                SortQuick(arr, left, pivot - 1);
            }

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

What I want to know is, what is happening in the process when the 2 inner "if statements" become false. Why the recursion does not terminate? Where the next process will go and why?

I just got confused because when I tried to follow the breakpoints step by step, I didn't understand what really happened. The left = 0 and right = 2, but when I continued to follow the breakpoints, it became left = 5 and right = 9. Anyway, 4 is my first pivot and I entered 10 numbers. So basically, I knew that the code was starting to partition the right side as it's done with left side; That's why the left variable became 5 and the right became 9. I just don't get how this happens and which part of this function made left = 5 and right = 9 from left = 0 and right = 2.

This is what I've entered: (5 1 9 2 3 8 4 7 6 10)

I've already understand the Partition Process, so I didn't include it in my question. Thanks in advance. :)

Amadan · Accepted Answer · 2017-01-31 07:11:17Z

3

One is often taught that a recursive function always must have two cases: a recursive case and a terminating case. What is often not clear is that the only thing required of the terminating case is to not recurse.

At leaf nodes of the recursion graph, you have calls where left < right is not true (e.g. left == 0 and pivot == 1 will lead to calling SortQuick(arr, 0, 0)), and the function is a no-op (more to the point, it exits without recursing further).

edited Jan 31, 2017 at 7:11

answered Jan 31, 2017 at 6:58

Amadan

200k23 gold badges252 silver badges321 bronze badges

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

3 Comments

Syntax Error Over a year ago

Ok, the recursion will be terminated if left >= right.. Then, where the next process will go if it becomes false in two inner "if statements"

Amadan Over a year ago

Back up the call stack. As I alluded to in the answer, quick-sort will create a binary-graph kind of structure, where each call to quick-sort will spawn 0-2 new calls to quick-sort. For example, sort arr will spawn sort [5, 1, 2, 3, 4] and later sort [9, 8, 7, 6, 10]; sort [5, 1, 2, 3, 4] will want sort [1, 2] and later sort [5, 3, 4]; sort [1, 2] will spawn sort [1] and later sort [2]. sort [1] doesn't do anything, so sort [2] launches; that also exits, then sort [1, 2] is done and sort [5, 3, 4] can do its job.

code_dredd Over a year ago

@SyntaxError When the function reaches a "base case" and stops recursing, it simply exits back to the previous recursive calls already made that are still on the stack waiting to exit themselves. Eventually, the initial call that started it all is reached and exits, completing the process.

Community · Accepted Answer · 2017-05-23 12:33:32Z

The code needs a fix, the fixed line is commented:

    static public void SortQuick(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int pivot = Partition(arr, left, right);

            if (pivot - 1 > left)    // this line fixed
            {
                SortQuick(arr, left, pivot - 1);
            }

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

Partition() apparently chooses (low + high)/2 as the pivot index. The program sorts the data depth first, left first. The first instance left == 0, right == 9, so Partition returns (0+9)/2 = 4. The next instance has left == 0, right == 3, so Partition returns 2. The next instance has left = 0, right = 1, pivot = 1, which is a base case so SortQuick just returns. Since pivot of 2+1 is not < 3, that is also a base case, so SortQuick just returns again. The next instance has left = 5, right = 9, pivot = 7. See if you can follow that part from here.

The base case occurs when (pivot - 1 <= left) or (pivot + 1 >= right), when the partition size is either 2 or 3, in which case Partition() has sorted that part of the original array, and SortQuick just returns.

This is a duplicate of

How the recursion in Quicksort algorithm works?

Collectives™ on Stack Overflow

How the recursive function terminated in Quicksort Algorithm?

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related