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();
}

• Loki Astari: It may be tagged C++ but this looks more like C code. You need to learn to utilize the standard library more.
• Jamal: That improved code may be put into a self-answer instead, if further review is not needed.

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;
}

• Nils: Thanks for the review! I know about iostream, however I hate the additional typing required to use it.
• UncleBens: std::swap should rather be used as using std::swap; swap(x, y); - This will allow argument-dependent lookup to use user-defined overloads of swap in other namespaces.
• Nobody moving away from SE: Is there any reason why you did not suggest using std::partition?
• Nils: I did not know about std::partition, I really have to look into this.
• Ryan Dougherty: I'm not seeing the bug in that code you say has one - care to point out what it is?

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);
}

• Snowhawk: Don't use decltype(*begin) to return the underlying type. decltype(*begin) doesn't behave the same as std::iterator_traits<it_t>::value_type (see a proxy class example of std::vector<bool>). Use std::distance to calculate the elements between iterators (still constant time for your random access iterators, linear time for others). If you are suggesting c++11, don't use rand(). Instead, write a random selector with the <random> library. Use PascalCase for user-defined class/type names (Iter_t, Elem_t).
• Nils: Thx for the comment! But the link to the proxy class example is broken.
• Nils: However I do not understand why I should use distance instead of just minus is there any case where minus would not work?
• Emily L.: @Nils std::distance is usable on InputIterator whereas operator - is only required for RandomAccessIterator. In short std::distance allows template code to function for a broader range of iterator types.