Ошибка сегмента с алгоритмом подсчета инверсий

Question

Я работаю над программой, которая реализует подсчет инверсий с помощью алгоритма сортировки слиянием.

Когда я тестирую свою программу с заданными тестами. Я испытал ошибку сегментации, которую я не могу найти причину.

Один тестовый пример показан в следующих кодах:

    int inputArray[5] = {5,4,3,2,1};
    inversionCount Inversion(inputArray, 5);
    count = Inversion.totalinversionCount(0, 4);

Программа дает правильный ответ как 10.

Еще один тестовый пример:

    int inputArray[15] = {9, 12, 3, 1, 6, 8, 2, 5, 14, 13, 11, 7, 10, 4, 0};
    inversionCount Inversion(inputArray, 15);
    count = Inversion.totalinversionCount(0, 14);

Программа дает ответ как 48, в то время как правильный ответ - 56. Я попытался отладить программу, напечатав элементы array[] в классе. Кажется, в конструкторе скопированный массив [] равен {9 12 3 1 6 8 2 5 14 13 11 7 10 4 0}. Однако, когда программа переходит к подсчету, массив элементов класса [] изменяется на {0 12 3 1 6 8 2 5 14 13 11 7 10 4 0}. Первый элемент изменился на 0 с 9. Я не знаю почему.

Последний контрольный пример:

    int inputArray[100] = { 4, 80, 70, 23, 9, 60, 68, 27, 66, 78, 12, 40, 52, 53, 44, 8, 49, 28, 18, 46, 21, 39, 51, 7, 87, 99, 69, 62, 84, 6, 79, 67, 14, 98, 83, 0, 96, 5, 82, 10, 26, 48, 3, 2, 15, 92, 11, 55, 63, 97, 43, 45, 81, 42, 95, 20, 25, 74, 24, 72, 91, 35, 86, 19, 75, 58, 71, 47, 76, 59, 64, 93, 17, 50, 56, 94, 90, 89, 32, 37, 34, 65, 1, 73, 41, 36, 57, 77, 30, 22, 13, 29, 38, 16, 88, 61, 31, 85, 33, 54 };
    inversionCount Inversion(inputArray, 100);
    count = Inversion.totalinversionCount(0, 99);

Программа сталкивается с ошибкой сегментации на этапе построения. Отладка показывает паузы программы при копировании массива [] в массив [].

Signal received: SIGSEGV (Segmentation fault)
For program algorithm_design_i_week_1, pid 23,328
You may discard the signal or forward it and you may continue or pause the process

Моя программа приведена ниже. Пожалуйста, помогите мне выяснить причину ошибки сегментации. Большое спасибо.

inversionCount.h

#ifndef INVERSIONCOUNT_H
#define INVERSIONCOUNT_H

#include <iostream>

using namespace std;   

class inversionCount {
private:
    int length;
    int array[];

public:
    inversionCount(int Array[], int Length);
    int splitCount(int first, int mid, int last);
    int totalinversionCount(int first, int last);
};

#endif /* INVERSIONCOUNT_H */

inversionCount.cpp

#include "inversionCount.h"

inversionCount::inversionCount(int Array[], int Length) {
    length = Length;
    for (int i = 0; i < length; i++) 
        array[i] = Array[i];
}

int inversionCount::splitCount(int first, int mid, int last) {
    int first1 = first, last1 = mid;
    int first2 = mid + 1, last2 = last;
    int tempArray[length];
    int i = first;
    int totalSplitCount = 0;
    while (i < last && first1 <= last1 && first2 <= last2) {
        if (array[first1] < array[first2]) {
            tempArray[i] = array[first1];
            first1++;
            i++;
        }
        else {
            tempArray[i] = array[first2];
            totalSplitCount += last1 + 1 - first1;   
            first2++;
            i++;
        }           
    }
    while (first1 <= last1) {
        tempArray[i] = array[first1];
        first1++;
        i++;
    }   
    while (first2 <= last2) {
        tempArray[i] = array[first2];
        first2++;
        i++;
    }  
    for (int j = first; j < last + 1; j++) 
        array[j] = tempArray[j];
    return totalSplitCount;
}

int inversionCount::totalinversionCount(int first, int last) {    
    int totalCount = 0;
    if (first < last) {
        int mid = (first + last) / 2;
        totalCount = totalinversionCount(first, mid) + totalinversionCount(mid + 1, last) + splitCount(first, mid, last);
    }       

    return totalCount;
}

countDriver.cpp

#include "inversionCount.h"

int main(int argc, char** argv) {
    int inputArray[5] = {5,4,3,2,1};

    inversionCount Inversion(inputArray, 5);
    int count = 0;
    count = Inversion.totalinversionCount(0, 4);
    cout<<"The number of inversions is "<<count<<endl;
    return 0;
}

Answer 1

int array[]; не является допустимым C++ как определение переменной-члена. Ваш компилятор должен разрешить это как расширение, но в этом случае это означает, что "для массива не выделено места, но мы сделаем что-то вроде:

A* pA = static_cast<A*>(malloc(sizeof(A) + Length*sizeof(int));

Вы этого не делаете, поэтому, когда вы пишете в массив, вы перезаписываете некоторые случайные биты памяти, так что случается что-то плохое.

Лучше всего использовать std::vector,

class inversionCount {
private:
    std::vector<int> array;

public:
    inversionCount(int Array[], int Length) : array(Array, Array+Length) {}
    int splitCount(int first, int mid, int last);
    int totalinversionCount(int first, int last);
};

Еще один комментарий: гораздо лучше использовать size_t как тип длин и смещений в массивах и контейнерах - это то, что использует библиотека C++. size_t это тип без знака, поэтому, используя тот же тип, что и библиотека, вы избежите трудных проблем с "несоответствием со знаком / без знака". (Эффекты часто не те, которые вы ожидаете.)