在这个合并排序算法中我应该把反转计数器放在哪里?

问题描述 投票:0回答:1

我正在尝试计算 100,000 个整数数组的合并排序过程中发生的反转次数。数组中的值没有特定的顺序。我的问题很简单,在合并排序算法中,我将在哪里应用反转计数器?下面是合并排序算法本身,之后的图像是我建议放置反转计数器的位置。文件读取正确并且合并排序工作正常,我只是问我的反转计数器的放置是否准确。任何建议将不胜感激!

清晰说明:主要区别位于 MergeSort 函数

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

void mergeSort(vector<int>&);
void merge(vector<int>&, vector<int>&, vector<int>&);


int main()
{
    int size = 0, n, numValues = 0;
    ifstream myFile;
    myFile.open("IntegerArray.txt");
    vector<int> array;
    
    if (myFile.is_open())
    {
        while (myFile >> n)
        {
            array.push_back(n);
            numValues++;
        }

        //for (int i = 0; i < 100000; i++)
            //cout << array.at(i) << " ";

        cout << "\nValues counted: " << numValues;
    }
    myFile.close();

    mergeSort(array);

    cout << "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";

    for (int i = 0; i < 100000; i++)
        cout << array[i] << "\n";
        
}

void mergeSort(vector<int> &array)
{
    if (array.size() <= 1) return;

    int middle = array.size() / 2;
    vector<int> left;
    vector<int> right;

    for (int i = 0; i < middle; i++)
        left.push_back(array[i]);
    for (int j = 0; j < (array.size() - middle); j++)
        right.push_back(array[middle + j]);

    
    mergeSort(left);
    mergeSort(right);
    merge(left, right, array);
    
}

 void merge(vector<int> &left, vector<int> &right, vector<int> &array) 
{
    int leftSize = left.size();
    int rightSize = right.size();
    int i = 0, l = 0, r = 0;

    while (l < leftSize && r < rightSize)
    {
        if (left[l] < right[r])
        {
            array[i] = left[l];
            i++;
            l++;
        }
        else
        {
            array[i] = right[r];
            i++;
            r++;
        }
    }

    while (l < leftSize)
    {
        array[i] = left[l];
        i++;
        l++;
    }
    
    while (r < rightSize)
    {
        array[i] = right[r];
        i++;
        r++;
    }

}

带有反转计数器的代码:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

void mergeSort(vector<int>&, int&);
void merge(vector<int>&, vector<int>&, vector<int>&, int&);


int main()
{
    int size = 0, n, numValues = 0;
    int numInversion = 0;
    ifstream myFile;
    myFile.open("IntegerArray.txt");
    vector<int> array;
    
    if (myFile.is_open())
    {
        while (myFile >> n)
        {
            array.push_back(n);
            numValues++;
        }

        //for (int i = 0; i < 100000; i++)
            //cout << array.at(i) << " ";

        cout << "\nValues counted: " << numValues;
    }
    myFile.close();

    mergeSort(array, numInversion);

    cout << "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";

    for (int i = 0; i < 100000; i++)
        cout << array[i] << "\n";
        
}

void mergeSort(vector<int> &array, int &inversionCount)
{
    if (array.size() <= 1) return;

    int middle = array.size() / 2;
    vector<int> left;
    vector<int> right;

    for (int i = 0; i < middle; i++)
    {
        left.push_back(array[i]);
        inversionCount++;
    }
    
    for (int j = 0; j < (array.size() - middle); j++)
    {
       right.push_back(array[middle + j]);
       inversionCount++;
    }

    
    mergeSort(left,inversionCount);
    mergeSort(right,inversionCount);
    merge(left, right, array, inversionCount);
    
}

 void merge(vector<int> &left, vector<int> &right, vector<int> &array, int &inversionCount) 
{
    int leftSize = left.size();
    int rightSize = right.size();
    int i = 0, l = 0, r = 0;

    while (l < leftSize && r < rightSize)
    {
        if (left[l] < right[r])
        {
            array[i] = left[l];
            i++;
            l++;
            
        }
        else
        {
            array[i] = right[r];
            i++;
            r++;

        }
    }

    while (l < leftSize)
    {
        array[i] = left[l];
        i++;
        l++;
    }
    
    while (r < rightSize)
    {
        array[i] = right[r];
        i++;
        r++;
    }

}
c++ mergesort inversion
1个回答
0
投票

从您的评论来看,您似乎走在正确的道路上。

但是,让我们看一些随机数的情况,并跳过前几次合并。我们将采用 [4,5,7,8,9] 和 [1,2,3,5,6] 的情况。也许已经计算了一些反转,但我们只是从这里开始。

首先,我们检查[4]是否大于[1]。确实如此,所以我们必须增加反转计数器。然而,在这种情况下,[4] 也大于 [2] 和 [3],这也必须进行检查。

问题是,我们怎样才能做到这一点?好吧,当我们意识到 [4] 大于 [1] 时,我们可以在右侧数组内启动另一个循环,增加反转计数器,直到遇到大于或等于 4 的值,然后停止。因此,在本例中,我们对 [4] 对 [1]、[2] 和 [3] 进行+1,然后在右侧停止[5]。这样我们就剩下+3,然后我们在新数组中放入 4,并从 left[5] 开始,再次向上计数。

显然,在开始检查之前我们必须保存 right[1] 的索引,否则 MergeSort 算法可能会搞砸。

这是一种幼稚的方法,因为当我们查看 left[5] 时,实际上没有理由一路倒数,因为我们知道 left[5] > left[4],并且我们已经知道 left [4] 大于 right[] 数组中的几个值。对于 100,000 个值之类的值,这种天真可能会导致您的程序速度明显减慢。

© www.soinside.com 2019 - 2024. All rights reserved.