Quicksort in C++

Question

Here is the implementation I ended up with. Please post your feedback!

#include <cstdio>
#include <cstdlib>

#include <iostream>

inline void swap(int * const a, const int i, const int j) {

    const int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

void printArray(int *a, int len) {
    for(int i=0; i<len; i++)
        printf("%i ", a[i]);
    printf("\n");
}

void qsort(int * const a, const int len) {

    if(len < 2)
        return;

    const int pivot = a[rand() % len];

    printf("Choosed pivot %i\n", pivot);

    int lower = 0;
    int upper = len - 1;

    while(true) {

        while(a[lower] < pivot)
            lower++;

        while(a[upper] > pivot)
            upper--;

        printArray(a, len);

        if(lower == upper)
            break;

        swap(a, lower, upper);
    }

    printf("First Part ");
    printArray(a, lower);
    printf("Second Part ");
    printArray(a + lower + 1, len - lower - 1);
    printf("\n");

    qsort(a, lower);
    qsort(a + lower + 1, len - lower - 1);
}

int main() {

    int a[] = {1, 7, 3, 6, 5, 9, 2, 0, 4, 8};
    int len = sizeof(a)/sizeof(int);

    qsort(a, len);
    printArray(a, len);

    std::cin.get();
}

Answer 1

#include <cstdio>
#include <cstdlib>

#include <iostream>

If you're writing C++ prefer cout and cin provided by iostream. They provide much better type-safety compared to their C counterparts. OTOH, you can still use printf and scanf if you don't need the extra flexibility provided by C++ streams and you want to keep overhead to a minimal. At any rate, it doesn't make sense to include both headers here -- you're either using one or the other.

---

inline void swap(int *const a, const int i, const int j) 
// ...

You don't need to write your own swap. The standard library provides a fully working std::swap which you can call like this:

std::swap(a[lower], a[upper]);

---

Note that const isn't really adding anything here for your qsort prototype since everything's pass-by-value. A subtle point is that pointer *a below is also pass-by-value. Changing *a in qsort won't affect where the original 'a' pointers to(the one passed by main).

void qsort(int * const a, const int len)
// ...

This qsort signature is more reminiscence of a C-style function than C++. In C++ it's more common to accept a range to sort by templatizing the parameters with iterator types. Something more akin to this for example:

template <class RANDOMIT>
void qsort(RANDOMIT begin, const RANDOMIT &end);

This is well covered in other quicksort questions already. Take a look here and here for a more detailed explanation and other ideas you can explore.

---

I would also factor out the partitioning code to its own function just to keep the tasks well-defined.

while(true) {
    while(a[lower] < pivot)
        lower++;
    while(a[upper] > pivot)
        upper--;

    printArray(a, len);

    if(lower == upper)
        break;

    swap(a, lower, upper);
}

There's also a bug lurking above -- duplicate items will cause an infinite loop. A possible fix might be:

while(true) 
{
    // ...
    if(lower >= upper) break;

    if(a[lower] != a[upper]) { std::swap(a[lower], a[upper]); }
    ++lower, --upper;
}

Answer 2

I understand that passing the length around can be useful if you pass dynamic arrays to your functions, but you could still write some reusable helper functions to handle statically-sized arrays:

template<typename T, std::size_t N>
std::size_t size(const T(&)[N])
{
    return N;
}

With this function, you can write:

int a[] = {1, 7, 3, 6, 5, 9, 2, 0, 4, 8};
int len = size(a);

---

You are using std::rand, but you don't seed it with std::srand first. Anyway, if you have a C++11 compiler, try to use the new <random> module instead. Standard methods that may use std::rand, such as std::random_shuffle are even deprecated in C++14.

Answer 3

@Victor: Cover all the points I wanted:

So just one very minor not pick.

int a[] = {1, 7, 3, 6, 5, 9, 2, 0, 4, 8};
int len = sizeof(a)/sizeof(int);

Prefer to define this in terms of the actual elements. Then if you change the type of the array you only need to change in one place:

int len = sizeof(a)/sizeof(a[0]); // a[0] will always have the correct type even if you
                                  // change the underlying type of the array. And since
                                  // is evaluated at compile time will always work.

Comment 1:

while(a[lower] < pivot)
    lower++;
while(a[upper] > pivot)
    upper--;

Which set do elements that are equal to the pivot go into?

Comment 2:

    if(lower == upper)
        break;

How often will that happen?

Answer 4

With C++11 and std::partition the code is waaay smaller and easier to read, I ended up with:

template <typename it_t>
void qsort(it_t begin, it_t end)
{
    typedef decltype(*begin) elem_t;

    size_t length = end - begin;

    if (length < 2)
    {
        return;
    }

    elem_t pivot = *(begin + ( rand() % length));

    it_t newPivotPos = partition(begin, end, [=] (elem_t elem) { return elem < pivot; });

    qsort(begin, newPivotPos);
    qsort(newPivotPos, end);
}