Two slightly Different implementations of Quick_Sort

[Arslan7041]

I'm trying to brush up on my sorting implementation so I decided to implement Quick Sort. Now, just to experiment, I implemented it in two slightly different ways, and expected both to work. However, only IMPLEMENTATION 1 works, while the other fails, and I can't seem to figure out why.

IMPLEMENTATION 1: (This one works)

#include <iostream>

int main()
{
    int A[] = {5, 9, 12, 15, 0, 1, 5, 10};
    const int SIZE = sizeof(A)/sizeof(A[0]);

    Quick_Sort(A, 0, SIZE-1); // call with SIZE-1

    for(int i : A) std::cout << i << " ";

    std::cout << "\n";
}

void Quick_Sort(int A[], int p, int r)
{
    if(p < r)
    {
        int q = Partition(A, p, r);
        Quick_Sort(A, p, q-1);
        Quick_Sort(A, q+1, r);
    }
}

int Partition(int A[], int p, int r)
{
    int x = A[r]; // pivot is last element
    int i = p-1;
    for(int j = p; j < r; j++) // go up to second-to-last element
    {
        if(A[j] <= x)
        {
            i++;
            std::swap(A[j], A[i]);
        }
    }

    std::swap(A[i+1], A[r]); // swap with last element

    return i+1;
}

IMPLEMENTATION 2: (This one doesn't work)

#include <iostream>
int main()
{
    int A[] = {5, 9, 12, 15, 0, 1, 5, 10};
    const int SIZE = sizeof(A)/sizeof(A[0]);

    Quick_Sort(A, 0, SIZE); // call with SIZE

    for(int i : A) std::cout << i << " ";

    std::cout << "\n";
}

void Quick_Sort(int A[], int p, int r)
{
    if(p < r-1)
    {
        int q = Partition(A, p, r);
        Quick_Sort(A, p, q-1);
        Quick_Sort(A, q+1, r);
    }
}

int Partition(int A[], int p, int r)
{
    int x = A[r-1]; // pivot is last element
    int i = p-1;
    for(int j = p; j < r-1; j++) // go up to second-to-last element
    {
        if(A[j] <= x)
        {
            i++;
            std::swap(A[j], A[i]);
        }
    }

    std::swap(A[i+1], A[r-1]); // swap with last element

    return i+1;
}

As you can see, first I called it using SIZE-1, and it worked. Then I wanted to call it by sending the array how we 'normally' send arrays i.e. by sending SIZE, and adjusting the 'r' variable in the other functions. I thought it would produce the exact same result, but the elements are not in sorted order.

What is going on here?

[ne555]

in the second snip
`p': first element
`r': one past last element

        int q = Partition(A, p, r); //A[q] has the pivot
        //Quick_Sort(A, p, q-1); //you never reach A[q-1]
        Quick_Sort(A, p, q);
        Quick_Sort(A, q+1, r);

[Arslan7041]

Ah, I see. So I wasn't being consistent when changing the code to the "one past last element" style.

Thank you, it worked.