CODEWITHSUNDEEP
c++quicksort
A. Duff
A. Duff

Reputation: 4309

Segmentation fault when programming Quicksort in C++

I'm trying to program the first algorithm on this page in C++. This is what I get when I adapt this to this language:

void quicksort (vector<int>& numbers) {
      int leftSize = numbers.size() / 3
      , rightSize = numbers.size() - leftSize;
      vector<int>::iterator pivot = numbers.end() - rightSize; //Choose one third of the way through as the pivot.
      vector<int> left;
      vector<int> right;

      if(numbers.size() <= 1) {
          return;
      }

      //Place numbers less than the pivot on the left side and numbers greater on the right side
      for(vector<int>::iterator x = numbers.begin(); x < numbers.end(); x++) {
          if(*x < *pivot) {
              left.push_back(*x);
          } else {
              right.push_back(*x);
          }
      }

      quicksort(left);
      quicksort(right);

      //Concatenate the arrays
      numbers.clear();
      numbers.insert(numbers.end(), left.begin(), left.end());
      numbers.insert(numbers.end(), right.begin(), right.end());
}

But this is giving an error Segmentation fault (core dumped). I'm only testing this on a vector of size 20, so it shouldn't be that I'm running out of memory. What I've been able to find out is that it's the call to quicksort(right) that's causing the problem. Commenting out only that line and leaving quicksort(left) produces no runtime errors (although the vector obviously doesn't come out sorted).

Any ideas why quicksort(left) would work, but not quicksort(right)?

Upvotes: 0

Views: 455

Answers (1)

Beta
Beta

Reputation: 99084

If you choose the minimum element of a vector as a pivot, then all elements (including the pivot) will go into right. You then call quicksort on right, which is the same vector you had before. Each call to quicksort makes an identical call to quicksort, you quickly exceed the maximum depth of the stack and get a segfault.

Upvotes: 3

Related Questions