Быстрая сортировка в C ++ с std :: vector, EXC_BAD_ACCESS code 2 - PullRequest
Новая
       23

Быстрая сортировка в C ++ с std :: vector, EXC_BAD_ACCESS code 2

0 голосов
/ 17 января 2020

VS Код перехватывает это исключение, когда я запускаю алгоритм быстрой сортировки: EXC_BAD_ACCESS (code = 2, address = 0x7ffeef3ffff c). Это происходит в первой строке раздела (): 

int i = p;

Я попытался реализовать алгоритм Кормена: http://www.cs.fsu.edu/~lacher/courses/COP4531/lectures/sorts/slide09.html

Почему я не могу получить доступ к переменная р? Выпущено ли оно, и если да, то как мне это исправить?

Мой код 

//.h file
void sortVector(vector<int> &vec, int p=0, int r=-2);
int partition(vector<int> &vec, int p, int r);

//.cpp file
int partition(vector<int> &vec, int p, int r) {
    int i = p;
    for (int j = p; j <r-1; ++j) {
        if (vec[j] < vec[r-1]) {
            swap(vec[j], vec[r-1]);
            i++;
        }
        swap(vec[i], vec[r-1]);
    }
    return i;
}

void sortVector(vector<int> &vec, int p, int r) {
    if (r == -2) {
        r = vec.size();
    }
    if (p-r<1) {
        int q = partition(vec, p, r);
        sortVector(vec, p, q);
        sortVector(vec, q+1, r);
    }

}

Я включаю "std_lib_facilities.h" из Stroustrup: принципы программирования и практика использования C ++.

Ответы [ 2 ]

1 голос
/ 17 января 2020

Были проблемы в обеих функциях:

partition ():

  • первый своп имел неверные аргументы.
  • второй своп пришлось удалить из-за oop (предложено Фаруком Хоссейном)
  • if (vec[j] < vec[r-1]) стало if (vec[j] <= vec[r-1])

sortVector ():

  • if (p-r<1) стал, если (p<r)

Рабочий код ниже. 

int partition(vector<int> &vec, int p, int r) {
    int i = p;
    for (int j = p; j <r-1; ++j) {
        if (vec[j] <= vec[r-1]) {
            swap(vec[i], vec[j]);
            i++;
        }
    }
    swap(vec[i], vec[r-1]);
    return i;
}
void sortVector(vector<int> &vec, int p, int r) {
    if (r == -2) {
        r = vec.size();
    }
    if (r>p) {
        int q = partition(vec, p, r);
        sortVector(vec, p, q);
        sortVector(vec, q+1, r);
    }

}
1 голос
/ 17 января 2020

Вам нужно написать swap(vec[i], vec[r-1]); из for l oop.

Так и должно быть - 

//.cpp file
int partition(vector<int> &vec, int p, int r) {
    int i = p;
    for (int j = p; j <r-1; ++j) {
        if (vec[j] < vec[r-1]) {
            swap(vec[j], vec[r-1]);
            i++;
        }
    }
    swap(vec[i], vec[r-1]);

    return i;
}
...