Сортировка слиянием на основе CLRS Введение в алгоритмы с подсчетом инверсий на C++

Что ж, прошли месяцы, и хотя я сделал работу над реализацией кода для возврата отсортированного массива, ошибка в подсчете инверсий все еще была. Сегодня я работал над этим и решил его, так что вот он.

Во-первых, в последнем методе mergeInvCount доступ к arr осуществляется с индексом, основанным на 1, поэтому он не работает, исправлено вычитание 1 для доступа с индексом, основанным на 0.

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

Когда элемент в левом вспомогательном массиве больше, чем элемент в правом вспомогательном массиве, мы должны подсчитать 1 инверсию для этого числа и 1 для каждого из других элементов после него, кроме «бесконечного» комодина. Поскольку вспомогательные массивы упорядочены из-за рекурсивных вызовов, это правильно.

Это работает, когда левый вспомогательный массив начинается с индекса 1, потому что вычитание (mid - i) возвращает количество элементов, оставшихся в упорядоченном вспомогательном массиве, без учета комодина.

Но когда мы объединяем массивы и левая часть не начинается с 1, вычитание не возвращает правильное количество элементов после фактического индекса в массиве.

Таким образом, решение этой проблемы состоит в использовании n1, в котором хранится количество элементов в левом вспомогательном массиве. Таким образом, (n1 - i) возвращает правильное число.

Вот рабочий код:

int mergeSortInvCount(vector<int> &arr, int izq, int der);
int mergeInvCount(vector<int> &arr, int izq, int mitad, int der);

void invCountRecursivo(vector<int> &arr, int n){

    int numInversiones = mergeSortInvCount(arr, 1, n);
    cout << "Num inversiones:" << numInversiones << endl;
    cout << "Ordered array, ascendant order" << endl;
    for(int i=0; i < n; i++){
        cout<<arr[i]<<endl;
    }
}

int mergeSortInvCount(vector<int> &arr, int izq, int der){

    int invCount = 0;

    if(izq < der){

        int mitad = (izq + der)/2;
        invCount = mergeSortInvCount(arr, izq, mitad);
        invCount += mergeSortInvCount(arr, mitad+1, der);
        invCount += mergeInvCount(arr, izq, mitad, der);
    }

    return invCount;
}

int infinito = numeric_limits<int>::max();

int mergeInvCount(vector<int> &arr, int izq, int mitad, int der){

    int n1 = mitad - izq + 1;
    int n2 = der - mitad;

    int invCount = 0;

    vector<int> vectorIzq;
    vector<int> vectorDer;

    for(int k=0;k<n1;k++){

        vectorIzq.push_back(arr[izq+k-1]);
    }

    vectorIzq.push_back(infinito);

    for(int k=0;k<n2;k++){

        vectorDer.push_back(arr[mitad+k]);
    }

    vectorDer.push_back(infinito);

    int i = 0;
    int j = 0;

    for(int k = izq; k <= der; k++){

        if(vectorIzq[i] <= vectorDer[j]){

            arr[k-1] = vectorIzq[i];
            i++;
        }
        else{

            arr[k-1] = vectorDer[j];
            j++;
            invCount += (n1 - i);
        }
    }

    return invCount;
}

int main(){

    vector<int> v = {4,3,1,8,2};
    invCountRecursivo(v, 5);
    // Returns 6, the correct # of inversions of A

    return 0;
}