插入和合并排序不适用于大数据集 C++

Question

我一直在尝试为从文件中读取的数据集编写插入和合并排序。在测试我的代码时，我使用了一个小数据集（包括 6 个数字）并且我的程序运行完美。但是当我使用包含 1000000 个输入的更大数据集时，代码无法正常工作，我不明白为什么。我试图将向量的类型更改为 double 但它并没有解决问题。预先感谢您的所有帮助。

我的数据集包含如下数字：512069、12823、11628

这是我的代码：

  vector<int> readFile(string fileName);
    void display(vector<int> &vector);
    void insertionSort(vector<int> &vec);
    vector<int> merge(vector<int> left, vector<int> right);
    vector<int> mergeSort(vector<int> &m);

int main(int argc, const char * argv[]) {

    string fileName;
    cout<<"Enter input file name :";
    cin>>fileName;

    vector<int> numbersVec = readFile(fileName);
    display(numbersVec);

    cout<<"INSERTION SORT"<<"\n";
    insertionSort(numbersVec);
    display(numbersVec);

    cout<<"MERGE SORT"<<"\n";
    vector<int> neu = mergeSort(numbersVec);
    display(neu);


    return 0;
}


vector<int> readFile(string fileName){

    vector<int> numbers;
    ifstream in(fileName,std::ios::in);

    if(!in.is_open())
    {
        cout << "File Cannot be Opened" << endl;
    }

    else{

        int number;
        while (in >> number) {
            numbers.push_back(number);
        }
    }

    in.close();
    return numbers;
}


void display(vector<int> &vec) {

    for(int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << " ";
    }
    cout << "\n" << endl;

}


void insertionSort(vector<int> &vec) {

    long double i, j, tmp;

    for (i = 1; i < vec.size(); i++) {

        j = i;

        while (j > 0 && vec[j - 1] > vec[j]) {

            tmp = vec[j];
            vec[j] = vec[j - 1];
            vec[j - 1] = tmp;
            j--;

        }
    }
}


vector<int> merge(vector<int> tmpl, vector<int> tmpr){

    vector<int> res;

    while ((int)tmpl.size() > 0 || (int)tmpr.size() > 0) {

        if ((int)tmpl.size() > 0 && (int)tmpr.size() > 0) {

            if ((int)tmpl.front() <= (int)tmpr.front()) {

                res.push_back((int)tmpl.front());
                tmpl.erase(tmpl.begin());

            }

            else {

                res.push_back((int)tmpr.front());
                tmpr.erase(tmpr.begin());

            }

        }
        else if ((int)tmpl.size() > 0) {

            for (int i = 0; i < (int)tmpl.size(); i++)

                res.push_back(tmpl[i]);

            break;
        }

        else if ((int)tmpr.size() > 0) {

            for (int i = 0; i < (int)tmpr.size(); i++)

                res.push_back(tmpr[i]);

            break;

        }

    }

    return res;

}


vector<int> mergeSort(vector<int> &vec)
{
    if (vec.size() <= 1)

        return vec;

    vector<int> tmpl, tmpr, res;

    int mid = ((int)vec.size()+ 1) / 2;

    for (int i = 0; i < mid; i++) {

        tmpl.push_back(vec[i]);

    }

    for (int i = mid; i < (int)vec.size(); i++) {

        tmpr.push_back(vec[i]);

    }

    tmpl = mergeSort(tmpl);

    tmpr = mergeSort(tmpr);

    res = merge(tmpl, tmpr);

    return res;
}

Answer 1

你的算法看起来不错。这只是一个复杂的问题。如果算一下插入排序算法的while执行的次数，平均来说接近n(n-1)/2，其中n是你数据集的大小（见insertion sort).

如果 n=1.000.000，复杂度接近 500.000.000.000，这很长。

只需尝试在 main 中注释对 insertionSort 的调用，您的 main 函数应该提前结束。

请注意，即使您在 mergeSort 算法中执行（太多）多个 vector 副本，它也会提前终止。复杂度为 'n * log(n)'（参见 merge sort）。

插入和合并排序不适用于大数据集 C++

Insertion and Merge Sorts Does not Work on Big Data Sets C++

c++

sorting

mergesort

dataset

insertion-sort