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);
        }
    }

What do you mean can't work well? Provide information in the question instead of expecting us to glean it from the image. — therainmaker, Nov 15 '15 at 07:21
The process stopped at the green line, I can not find the reason. It is really frustrated. — WB Lee, Nov 15 '15 at 07:30
Usually you should include the textual error message in the question, rather than showing a screenshot. — 4ae1e1, Nov 15 '15 at 07:37
The error message is that "Thread 1: EXC_BAD_ACCESS (code = 2, address=0x7fff5f3fffd8)". The program stopped at the green line. — WB Lee, Nov 15 '15 at 07:42
@WBLee Use **Zombie** tool in **Insturments** to find out the cause of the problem, more details: http://stackoverflow.com/a/11717981/2128327 — Khaled.K, Nov 15 '15 at 07:51
@ Khaled A Khunaifer Thanks for the information about zombie toll! — WB Lee, Nov 15 '15 at 07:57

fghj · Accepted Answer · 2018-10-03T20:07:41.833

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

My quickSort() program cannot work well, why?

1 Answers1