CODEWITHSUNDEEP
c++segmentation-fault
Guille
Guille

Reputation: 652

c++ Thread: EXC_BAD_ACCESS(Code=2, address0x

I am playing around with quick sorting algorithm using a vector and templates. i am testing the algorithm 100, 1000 and 1M times. it works some some tests such as in sorting a random list, but when it is sorting a descending list i get the following error in xcode and running in terminal i get Segmentation fault: 11.

Thread: EXC_BAD_ACCESS(Code=2, address0x...

I am still a c++ beginner and i don't quite understand what i am doing wrong. Any Tips or possible solutions?

#include <iostream>
#include <cstdlib>
#include <vector>


template <class T>
class quickSort {

public:
    void sorting(std::vector<T>&);
    void quick(std::vector<T>&, const unsigned&, const unsigned&);
    unsigned counter;
};


template<class T>
void quickSort<T>::sorting(std::vector<T>& toSort)
{
    unsigned max = 0;
    max = (unsigned)(toSort.size()-1);
    quick(toSort, 0, max);

}

template<class T>
void quickSort<T>::quick(std::vector<T>& toSort, const unsigned& leftarg, const unsigned& rightarg)
{
  if (leftarg < rightarg) {

    T pivotvalue = toSort[leftarg];
    int left = leftarg - 1;
    int right = rightarg + 1;

  for(;;) {
      counter++;
    while (toSort[--right] > pivotvalue);
    while (toSort[++left] < pivotvalue);

    if (left >= right) break;

    T temp = toSort[right];
    toSort[right] = toSort[left];
    toSort[left] = temp;
  }

  T pivot = right;
  quick(toSort, leftarg, pivot);
  quick(toSort, pivot + 1, rightarg);
  }
}

Upvotes: 0

Views: 158

Answers (1)

user2693780
user2693780

Reputation:

leftarg is an unsigned int. During the first invocation of quick(), it has a value of 0. If you then subtract one from it (int left = leftarg - 1) the value overflows and you get UINT_MAX instead of -1. This leads to errors and segmentation faults since you use left as an index, and UINT_MAX is clearly outside the valid index range.

I recommend you familiarize yourself with debugging in C++ and go through your code step by step on a small input (say 5 values) to gain a better understanding.

Upvotes: 1

Related Questions