C++ quicksort practice midterm help please

Question

I'm having trouble with understanding my professor's pesudocode for this quicksort algorithm in his practice midterm question and was wondering if anyone can help me clarify how the sorting goes.

Pesudocode

void Sort(int A[], int a, int b)
{
    cout << "Sorting array between index" << a << " and Index " << b << endl;
    if(a>=b) return;
    int m = Partition(A, a, b);
    Sort(A, a, m-1);
    Sort(A,m+1, b);
}
void partition(int A[], int a, int b)
{
    int v = A[b];
    int x = a-1;
    for(int y = a; y <= b-1; y++)
    {
        if(A[y] < v)
        {
            Swap(A[x+1], A[y]);
            cout << "Swapped Item " << A[x+1] << " with item " << A[y] << endl;
            x++;
        }
    }
    Swap(A[x+1],A[b]);
    cout << "Swapped item " << A[x+1] << " with item " << A[b] << endl;
    return x+1;
}


Index:   0   1   2   3
Value:   9   6   7   5
--------------------------------------------------------------------

I don't know if I got it right because I was confused of "y <= b-1" in the forloop, making me think that "y <= 3-1" is "y <= 2" so I'm sorry if it gets confusing and I'm trying my best to understand this loop.

Okay, when I start the forloop in the partition of (int y = a; y <= b-1; y++), I compare A[y]< A[b]

Index:   0*  1   2   3*        
Value:   9   6   7   5

A[0] < A[3] = 9 < 7     is not true so I skip to the next element
A[1] < A[3] = 6 < 7     is true, Swap(A[x+1], A[y])

I think x = -1 because x = a-1 -> x = low-1 -> x = 0-1 -> x = -1

swap(A[x+1],A[x]) = swap(A[-1+1],A[3]) = swap(A[0], A[3])

x++ = x=0+1 = x=1

Swapped:

Index:   0   1   2   3        
Value:   5   6   7   9

After that, I got really lost here on what to do next. I know this is incorrect and I'd appreciate it if somebody can help walk me through the code so I can understand it easier. I appreciate it.

Also in question e of my practice midterm that relates to this quicksort code:

e) If the above algorithm is run with the above **Partition** routine,
   a stack overflow may occur in some cases. What are these cases? 
   Briefly explain why a stack overflow may occur in these cases and modify
   the Partition routine to minimize the probability of stack overflow.

I'm not sure how to answer it because I'm thinking that the quicksort stack overflow occurs either with a random pivot or problems with the recursion that gives the worst case of O(n^2).

Answer 1

The starting array is

Index:   0   1   2   3
Value:   9   6   7   5

(If your professor chose this, he chose oddly.) None of the first three values is less than the last, so control will pass through the for loop without performing any swaps.

Index:   0   1   2   3
Value:   9   6   7   5

Then Swap(A[x+1],A[b]); swaps the first and last elements:

Index:   0   1   2   3
Value:   5   6   7   9

and the function returns 0. The array has the property that no value from index 0 to index 3 is less than A[0], and Sort then calls

Sort(A, 0, -1);
Sort(A, 1, 3);

As for the stack overflow, you're right, it can happen in something close to the O(n) worst case, which is very rare with random data, but can happen with a certain kind of real-world data. You already have all the information you need to solve that part.