1 Вопрос: Получение «Ошибка сегментации: 11» при поиске числа инверсий с использованием сортировки слиянием в C ++

вопрос создан в Wed, May 8, 2019 12:00 AM

Я пишу программу на C ++, которая находит число инверсий в векторе, используя сортировку слиянием. Инверсия происходит, когда i-й элемент больше, чем j-й элемент, где i < j. Например, скажем, вектор { 1, 3, 5, 2 }, то есть 2 инверсии: {3,2} и 06 Функция {5,2} продолжает рекурсировать и делить вектор, пока длина подвектора не станет одним элементом. Функция countNsort выполняет сортировку слиянием для сортировки и подсчета количества инверсий.

Я пытался:

  1. Различные способы инициализации входного вектора. countNsortSplit, vector<int> a{2,1}; и vector<int> a; a={2,1};.
  2. Различные способы разбиения входного вектора на подвекторы. vector<int> a(2); a={2,1}; и vector<int> c(a.begin()+half, a.begin()+n);, где n - размер вектора.
  3. Различные IDE. Атомы дают мне это: vector<int> c(a.begin()+half, a.end());, CodeBlocks дает мне это: bash: line 1: 13763 Segmentation fault: 11 /tmp/cpp.out [Finished in 20.57s] для этой строки: error: expected expression.
a={2,1}:     
1
  1. Дополнительная информация: инверсия происходит, когда i-й элемент больше, чем j-й элемент, где i < j. Например, скажем, вектор равен {1,3,5,2}, тогда есть 2 инверсии: {3,2} и {5,2}. Функция countNsort продолжает рекурсировать и делить вектор до тех пор, пока длина подвектора не станет единственным элементом. Функция countNsortSplit выполняет сортировку слиянием для сортировки и подсчета количества инверсий.
    2019-05-08 15: 59: 17Z
  2. Вы вызываете неопределенное поведение здесь
    #include <stdio.h>
    #include <vector>
    #include <iostream>
    
    using namespace std;
    
    struct returnVal {
        int count;
        vector<int> sorted_array;
    };
    
    returnVal countNsortSplit(vector<int> left, vector<int> right, int n) {
        returnVal output;
        int count = 0;
        vector<int> merge;
        int i = 0;
        int j = 0;
        for (int k = 0; k < n; k++) {
            if (left[i] < right[j]) {
                merge[k] = left[i];
                i++;
            } else {
                merge[k] = right[j];
                j++;
                // increment count by the # of remaining elements in left
                count += left.size()-i;
            }
        }
        output.sorted_array = merge;
        output.count = count;
        return output;
    }
    
    returnVal countNsort(vector<int> a, int n) {
        returnVal output;
        if (n == 1) {
            output.sorted_array = a;
            output.count = 0;
            return output;
        } else {
            returnVal left;
            returnVal right;
            returnVal split;
            int half = n / 2;
            vector<int> b(a.begin(), a.begin() + half);
            vector<int> c(a.begin() + half, a.begin() + n);
            left = countNsort(b, half);
            right = countNsort(c, n - half); // need n-n/2 in case of odd length
            split = countNsortSplit(left.sorted_array, right.sorted_array, n);
            output.sorted_array = split.sorted_array;
            output.count = left.count + right.count + split.count;
            return output;
        }
    }
    
    int main() {
        vector<int> a(2);
        //a = {1,3,5,2};
        //a = {1,3,5,2,4,6};
        a = {2, 1};
        returnVal result;
        result = countNsort(a, a.size());
        cout << result.count << endl;
    }
    
    , прежде чем получить к нему доступ с помощью оператора индексации, необходимо сначала изменить размер вектора. Также не размещайте дополнительную информацию в комментариях. Вы всегда можете изменить свой вопрос.
    2019-05-08 16: 01: 45Z
  3. Подсказка: merge[k] имеет нулевой размер при инициализации. Чтобы добавить элементы: std::vector или push_back. Для фиксированного размера: emplace_back.
    2019-05-08 16: 22: 22Z
  4. Рекомендуем запускать такие программы с asan или valgrind. Иногда они улавливают проблему намного раньше, до того, как на самом деле проявится сегментация. YMMV
    2019-05-08 16: 26: 17Z
1 ответ                              1                         

В вашем коде есть несколько проблем:

  • Вы не определяете вектор назначения с правильным размером
  • Вы не проверяете, достигли ли std::array или i размера векторов j и left соответственно.
  • Инициализатор для вектора right в a имеет недопустимый синтаксис.

Обратите внимание, что вам не нужно передавать размеры векторов main() и countNsort.

Вот исправленная версия:

countNsortSplit

Обратите внимание, что было бы более эффективно и логично сортировать вектор на месте и возвращать счетчик инверсий:

#include <iostream>
#include <vector>

using namespace std;

struct returnVal {
    int count;
    vector<int> sorted_array;
};

returnVal countNsortMerge(vector<int> left, vector<int> right) {
    int leftSize = left.size();
    int rightSize = right.size();
    int n = leftSize + rightSize;
    int count = 0;
    vector<int> merge(n);
    int i = 0;
    int j = 0;
    for (int k = 0; k < n; k++) {
        if (i < leftSize && (j == rightSize || left[i] < right[j])) {
            merge[k] = left[i++];
        } else {
            merge[k] = right[j++];
            // increment count by the # of remaining elements in left
            count += leftSize - i;
        }
    }
    returnVal output;
    output.sorted_array = merge;
    output.count = count;
    return output;
}

returnVal countNsort(vector<int> a) {
    int n = a.size();
    if (n <= 1) {
        returnVal output;
        output.sorted_array = a;
        output.count = 0;
        return output;
    } else {
        int half = n / 2;
        vector<int> b(a.begin(), a.begin() + half);
        vector<int> c(a.begin() + half, a.begin() + n);
        returnVal left = countNsort(b);
        returnVal right = countNsort(c);
        returnVal result = countNsortMerge(left.sorted_array, right.sorted_array);
        result.count += left.count + right.count;
        return result;
    }
}

int main() {
    //int values[] = { 1, 3, 5, 2 };
    //int values[] = { 2, 1 };
    int values[] = { 1, 3, 5, 2, 4, 6 };
    vector<int> a(values, values + sizeof values / sizeof *values);
    returnVal result = countNsort(a);
    cout << result.count << endl;
    return 0;
}
    
1
2019-05-08 18: 05: 21Z
#include <iostream>
#include <vector>

size_t countNsortMerge(std::vector<int>& a, size_t start, size_t middle, size_t end) {
    std::vector<int> temp(a.begin() + start, a.begin() + middle);
    size_t i = 0;
    size_t leftSize = middle - start;
    size_t j = middle;
    size_t count = 0;
    for (size_t k = start; k < end; k++) {
        if (i < leftSize && (j == end || temp[i] < a[j])) {
            a[k] = temp[i++];
        } else {
            a[k] = a[j++];
            // increment count by the # of remaining elements in left
            count += leftSize - i;
        }
    }
    return count;
}

size_t countNsort(std::vector<int>& a, size_t start, size_t end) {
    if (end - start <= 1) {
        return 0;
    } else {
        size_t middle = start + (end - start) / 2;
        size_t leftCount = countNsort(a, start, middle);
        size_t rightCount = countNsort(a, middle, end);
        return leftCount + rightCount + countNsortMerge(a, start, middle, end);
    }
}

int main() {
    //int values[] = { 1, 3, 5, 2 };
    //int values[] = { 2, 1 };
    int values[] = { 1, 3, 5, 2, 4, 6 };
    std::vector<int> a(values, values + sizeof values / sizeof *values);
    size_t result = countNsort(a, 0, a.size());
    std::cout << result << std::endl;
    return 0;
}
источник размещен Вот