My quickSort() program cannot work well, why?

Question

If you can help me, really thanks! Below is my code to sort vectors of numbers (of type double). The number of elements in vec is 200,000.

The program stopped at the green line, after several seconds. The error message is that

"Thread 1: EXC_BAD_ACCESS (code = 2, address=0x7fff5f3fffd8)".

just like the picture:

/*This is block to call quickSort*/
void VectorDoubleSort:: sort(std::vector<double>& vec){
      int start = 0;
      int end = vec.size() - 1;
      quickSort(vec, start, end);
}




/*This block to fulfill the quickSort method*/
    void VectorDoubleSort:: quickSort(std::vector<double>& vec, int start, int end)
    {
        int pivot = (start + end) / 2;
        int smallIndex = start;

        if (start < end) {
            double tempA = vec[start];
            vec[pivot] = tempA;

            for (int i = start + 1; i <= end; i++) {
                if (vec[i] <= vec[start]) {
                    smallIndex += 1;
                    double tempB = vec[i];
                    vec[i] = vec[smallIndex];
                    vec[smallIndex] = tempB;
                }
            }

            double tempC = vec[start];
            vec[start] = vec[smallIndex];
            vec[smallIndex] = tempC;

            pivot = smallIndex;

            quickSort(vec, start, pivot - 1);
            quickSort(vec, pivot + 1, end);
        }
    }

Answer 1

First, here is wrong:

int pivot = (start + end) / 2;
double tempA = vec[start];
vec[pivot] = tempA;

you lost content of vec[pivot], after that here if (vec[i] <= vec[start]) you order your vector by value of vec[start], then pivot is start, then why the hell, you set pivot to (start + end) / 2;? And as you use in compare NOT saved value, but reread it from vec[start], which can be changed by swap operation in vector. And after all you order against start, but your index increased in ordering cycle for (int i = start + 1; i <= end; i++), so after iteration you have (of course if previous bugs was fixed): {pivot, sub array <= pivot, sub array > pivot}, so you need instead of just swap if do index from end to start + 1 you need move sub array <= pivot to start and insert pivot between, so the right solution if reuse as much your code is possible will be:

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <vector>

namespace VectorDoubleSort {
void sort(std::vector<double> &vec);
void quickSort(std::vector<double> &vec, int start, int end);
}

void VectorDoubleSort::sort(std::vector<double> &vec) {
  if (vec.empty())
    return;
  int start = 0;
  int end = vec.size() - 1;
  quickSort(vec, start, end);
}

/*This block to fulfill the quickSort method*/
void VectorDoubleSort::quickSort(std::vector<double> &vec, int start, int end) {
  if (start < end) {
    const double pivotVal = vec[start];
    int smallIndex = end;

    for (int i = end; i > start; --i) {
      if (vec[i] >= pivotVal) {
        std::swap(vec[i], vec[smallIndex]);
        --smallIndex;
      }
    }
    std::swap(vec[start], vec[smallIndex]);

    const int pivot = smallIndex;
    quickSort(vec, start, pivot - 1);
    quickSort(vec, pivot + 1, end);
  }
}

bool test(const std::vector<double> &arr) {
  std::vector<double> good = arr;
  std::sort(good.begin(), good.end());
  std::vector<double> my = arr;
  VectorDoubleSort::sort(my);
  std::copy(my.begin(), my.end(),
            std::ostream_iterator<double>(std::cout, ", "));
  std::cout << "\n";
  return my == good;
}

int main() {
  assert(test({}));
  assert(test({3., 1., 2., 17., 18., -1., -5.}));
  assert(test({3., 1., 2.}));
  assert(test({3., 2.}));
  assert(test({3.}));
  assert(test({3., 532523, 5235, 05325, 535, 5738157, 535, 501, 9780, 14}));
}

Note: I use c++11(initializer_list), but only for testing, so without tests you can reuse c++98 or c++03