Назначение в C ++ меняет номера - PullRequest
Новая
       4

Назначение в C ++ меняет номера

0 голосов
/ 10 февраля 2020

Я пишу быструю сортировку и получаю сегфо. Я попытался найти источник ошибки, и кажется, что в функции разделения я назначаю i, я получаю 15460, а для j я получаю -1. Я не мог понять, как это может произойти. 

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

int partition(std::vector<int>& A, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    while (true) {
        while (A[++i] < A[lo])
            if (i == hi) break;
        while (A[lo] < A[--j])
            if (j == lo) break;
        if (i >= j) std::swap(A[i], A[j]);
    }
    std::swap(A[lo], A[j]);
    return j;
}

void sort(std::vector<int>& A, int lo, int hi) {
    if (hi <= lo) return;
    int j = partition(A, lo, hi);
    sort(A, lo, j - 1);
    sort(A, j + 1, hi);
}

void sort(std::vector<int>& A) {
    std::random_device random_device;
    std::mt19937 rng(random_device());
    std::shuffle(std::begin(A), std::end(A), rng);
    sort(A, 0, A.size() - 1);
}

int main() {
    std::vector<int> V = {2, 1};
    sort(V);
    for (const auto& item: V) std::cout << item;
}

1 Ответ

1 голос
/ 10 февраля 2020

В вашей функции partition () вы вложили циклы while. Внешний никогда не завершается, как упомянуто 1201ProgramAlarm. Два внутренних цикла продолжают увеличивать / уменьшать i / j. Поскольку ++ i / - j выполняется по крайней мере один раз для каждого запуска внешнего, тогда как l oop, эти значения в конечном итоге покинут допустимый диапазон для доступа к массиву. И поскольку эти индексы используются для доступа к массиву, вы неизбежно получите этот segfault.

...