0
\$\begingroup\$

Please review the following quicksort implementation. qsort below is intentionally unstable, as partition reoders equal elements.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Ensures pivot is at position end.
template<typename Iter, typename T>
Iter part_pivot(Iter begin, Iter end, T pivot) {
  while (begin != end) {
    if (*begin < pivot)
      ++begin;
    else if (*--end < pivot)
      iter_swap(begin, end);
  }
  return begin;
}

template<typename Iter>
Iter part(Iter begin, Iter end) {
  typename iterator_traits<Iter>::value_type pivot = *begin;
  Iter mid = part_pivot(begin, end, pivot);
  // Ensure pivot is at position mid.
  iter_swap(--end, mid);
  return mid;
}

template<class Iter>
void quicksort(Iter begin, Iter end) {
  if (std::distance(begin, end) < 2)
    return;
  Iter mid = part(begin, end, *begin);
  quicksort(begin, mid);
  quicksort(++mid, end);
}

template<class T>
void quicksort(vector<T>& v) {
  quicksort(v.begin(), v.end());
}

template <class T>
void print(const vector<T>& v) {
  for (const T& t : v)
    cout << t << " ";
  cout << endl;
}

int main() {
  vector<int> v = {1,4,8,34,2,3,45,6,87,4,3};
  print(v);
  quicksort(v);
  print(v);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Probably shouldn't use the same names as functions in the standard library, unless yours are in a different namespace (and even then, I'm not sure reusing qsort is advisable. It isn't that great of a name unless you're using a 1970s-era compiler that limited identifier names to 6–8 characters.) Speaking of the standard library, why aren't you just using std::sort? That makes it hard to review the code: since you are including <algorithm>, I'd want to recommend using, e.g., std::swap, but then the existence of std::sort makes the whole exercise rather silly. \$\endgroup\$ – Cody Gray Jan 25 '17 at 12:08
  • \$\begingroup\$ Your sort recurses infinitely at qsort(mid, end); for me. \$\endgroup\$ – coderodde Jan 25 '17 at 13:13
  • \$\begingroup\$ I've updated the code, addressing both of your comments, @CodyGray. \$\endgroup\$ – daejk Jan 25 '17 at 15:45
1
\$\begingroup\$

Two problems with the code that I see immediately:

  1. if (std::distance(begin, end) <= 2) is wrong since it leaves an array like {2,1} untouched. This means that the code can screw up every time it recurses to an array of size 2.

  2. Iter partition(Iter begin, Iter end, const T& pivot): Passing pivot as const T& is a bad idea. When passed as const reference, when you perform the iter_swap, the value pointed to by begin changes and so does pivot. Hence running your code gives me a segfault but changing const T& to T takes care of the segfault.

Even if these are fixed, there is something more subtle. Suppose you try to sort an already sorted array like {1,1,1}. Partitioning this will return mid = begin. So unless you make an explicit check for a sorted array you will recurse infinitely on qsort(mid,end).

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks, this is helpful. 1 + 2 are easy to fix. The subtle non-termination bug occurs because partition neither places the pivot in the middle, nor always returns an iterator that is strictly inside the given interval. I'll see what the easiest fix is. \$\endgroup\$ – daejk Jan 25 '17 at 15:21
  • \$\begingroup\$ I've updated the code, care to take a look again? \$\endgroup\$ – daejk Jan 25 '17 at 15:44
  • 2
    \$\begingroup\$ I don't think it is good practice to update question and code after accepting an answer, it would have been better to ask as a new question. In any case, have you tested the code on simple vectors to see if they work? \$\endgroup\$ – Raziman T V Jan 25 '17 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.