C++ Quicksort Algorithm

Question

I am working on a quicksort algorithm implementation in c++ and I have not been able to get it to work as it should. I have researched several sources and my code looks flawless, but the array is not sorting as it should.

Here is my code:

#include <iostream>
using namespace std;

void quicksort(int[],int, int);
int partition(int[], int, int);

int main()
{
    int a[] = {5, 1, 9, 3, 8, 4, 1, 2, 6, 7};
    for (int i = 0; i < 10; i++)
    { 
        cout << a[i] << " ";
    }
    cout << endl;
    quicksort(a, 0, 9);
    for (int i = 0; i < 10; i++)
    {
            cout << a[i] << " ";
    }
    return 0;
}

void quicksort(int a[], int p, int r)
{
    if (p < r)
    {
            int q = partition(a, p, r);
            quicksort(a, p, q - 1);
            quicksort(a, q + 1, r);
   }
}

int partition(int a[], int p, int r)
{
    int x = a[r];
    int i = (p - 1);
    for (int j = p; j <= r-1; j++)
    {
        if (a[j] <= x)
        {
                i++;
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
        }
     }
     int tmp = a[i+1];
     a[i+1] = a[r];
     a[r] = a[tmp];
     return (i + 1);
}

When I run this code the following is displayed:

5 1 9 3 8 4 1 2 6 7
1 1 2 4 4 4 6 7 7 7

I am not sure what I am doing wrong here. Thanks for your help.

Answer 1

In the second to last line of your partition function you should have:

  a[r] = tmp;

instead of:

  a[r] = a[tmp];

You are overwriting parts of your array with other members instead of completing the third step of your swap.