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.

Have you tried stepping through with a debugger? Should help you see what's going on. — LiMuBei
– LiMuBei, Commented Mar 9, 2016 at 22:54
Also a good rule is when you are working with array indices, try to consistently use "<" and the upper bound one behind the end index in for loops. Mixing upper bounds as "last used", "one after last" and "<" and "<=" is confusing (apparently yourself as well...). E.g. if you have an array containing 5 elements, write the for loop like for (i = 0; i <5; i++) . — tofro
– tofro, Commented Mar 9, 2016 at 22:59

Tuffwer · Accepted Answer · 2016-03-09 23:01:54Z

9

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.

answered Mar 9, 2016 at 23:01

Tuffwer

1,04710 silver badges23 bronze badges

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

4 Comments

tfreiner Over a year ago

Good catch! However after the change, my program displays: 8 2 8 8 32767 9 32767 100001 7 for the output of the sorted array.

Tuffwer Over a year ago

@tfreiner I'm not sure. When I run your code at ideone (an online compiler) It appears to work correctly.

Tuffwer Over a year ago

@tfreiner If you continue having issues the values your getting suggest to me that something isn't being initialized somewhere properly, or you're reading out of bounds on the array but still in memory the program owns (hence no segfault) I would suggest doing what tofro says and step through with a debugger to see how the values change as your program executes. You could also write descriptive print statements if you don't know how to use a debugger, but it would be better to learn how to use the debugger

tfreiner Over a year ago

I figured it out I made a stupid mistake. I applied your edit to the wrong file. I runs perfectly now thanks!

Collectives™ on Stack Overflow

C++ Quicksort Algorithm

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related