STL implementation of quicksort

Question

The code is generic, trying to support both STL iterators and normal C pointer arithmetic.

#include <cstdio>
#include <vector>
template<typename I>
void quick_sort_step(const I left, const I right)
{
 auto pivot = *(left + (right - left) / 2);
 auto l = left;
 auto r = right;
 while (l <= r) {
 while (*l < pivot)
 ++l;
 while (*r > pivot)
 --r;
 if (l <= r)
 std::swap(*l++, *r--);
 }
 if (left < r)
 quick_sort_step(left, r);
 if (l < right)
 quick_sort_step(l, right);
}
template<typename I>
void quick_sort(const I begin, const I end)
{
 if (end - begin > 1)
 quick_sort_step(begin, std::prev(end));
}
int main()
{
 typedef std::vector<int> list;
 list l { 5, 0, 2, 4, 1, 3, 9, 8, 7, 6 };
 quick_sort(l.begin(), l.end());
 for (auto i : l) {
 printf("%i ", i);
 }
 return 0;
}

• Loki Astari: Currently it fails to compile. Because it can not see ::sort() before it is used. Use forward declaration or move quick_sort().
• Loki Astari: Code now works. Added forward declaration.
• Snowbody: What do you mean by "Any other choice for pivot works but not this one"? What results do you expect to see, and what do you see instead?
• Thomas Matthews: What are the types for l and r in your sort function? If they are pointers, the operation <= may not be valid. Usually, pointers need to be converted to an integral type before comparison. There is no check that right is greater than left. Are these pointers also?
• Valentin Galea: @ThomasMatthews the code is generic, trying to support both STL iterators and normal C pointer arithmetic

Answer 1

You need to somehow check or restrict your templates to iterators only.

The way you have it written, I can perform the following:

int main(void)
{
 const char a = '5';
 const char b = '$';
 sort(a,b);
 const int five = 5;
 const int zero = 0;
 sort(five, 0);
 return EXIT_FAILURE;
}

Also, you may want to clarify that your arguments, when they are pointers, are constant pointers to mutable data.

• Valentin Galea: I still want the algorithm to work on plain C arrays

Answer 2

• For generic template types, it's more common to use T. This would help take out the guesswork if one isn't already aware of the template statement.

• Your typedef is superfluous since it's only used once in main(), so just remove it. The new name itself doesn't add anything to the context anyway.

• Sure, you can still use C-style print functions in C++ if you'd like, but it still makes your code look less like C++. I would've expected it to be done with something more complex that doesn't look as great with std::cout, but such a print statement will still look the same with std::cout.