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

Question

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

Я пробовал:

1. Различные способы инициализации входного вектора.vector<int> a{2,1};, vector<int> a; a={2,1}; и vector<int> a(2); a={2,1};.
2. Различные способы разбиения входного вектора на подвекторы.vector<int> c(a.begin()+half, a.begin()+n); и vector<int> c(a.begin()+half, a.end());, где n - размер вектора.
3. Различные IDE.Atoms дает мне это: bash: line 1: 13763 Segmentation fault: 11 /tmp/cpp.out [Finished in 20.57s], CodeBlocks дает мне это: error: expected expression для этой строки: a={2,1}:.

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

Answer 1

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

• Вы не определяете вектор назначения с правильным размером
• Вы не проверяете, есть ли 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;
}

Обратите внимание, что сортировкавектор на месте и вернуть счетчик инверсии:

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