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

我一直在尝试为从文件中读取的数据集编写插入和合并排序。在测试我的代码时，我使用了一个小数据集（包含6个数字），并且我的程序完美运行。但是当我用一个更大的数据集与1000000输入代码不工作，我不明白为什么。我试图改变向量的类型来加倍，但它不能解决问题。非常感谢您的帮助。插入和合并排序不适用于大数据集C++

我的数据集包括像数字：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; 
}

来源

2016-10-08 Valentino

大数据集有哪些错误？永远循环或别的东西？在'insertionSort'中，'i'，'j'，'tmp'应该有'int'类型，但不是'long double'。你的'mergeSort'函数似乎效率低下（多个向量拷贝：合并可能就位）。 – Franck

它打印出INSERTION SORT后进入无限循环，我试图使用调试器，几乎不可能跟踪这么大的设置。我也将i，j，tmp更改为int，但它仍然没有脱离循环。 – Valentino

这是一个复杂性问题。您的插入排序是n（n-1）/ 2，其中n是您的矢量的大小。即使你的矢量只有100万个数据，你也要等很长时间。 – Franck

你的算法似乎罚款。这只是一个复杂的问题。如果您计算插入排序算法的while的执行次数，平均而言，它接近于n(n-1)/2，其中n是数据集的大小（请参阅insertion sort）。

如果n = 1.000.000，则其复杂度接近500.000.000.000，这非常长。

只需尝试对中的insertionSort进行评论，并且您的main函数应该提前结束。

请注意，即使您在mergeSort算法中多次使用vector副本，它也会提前终止。复杂性是'n * log（n）'（见merge sort）。

来源

2016-10-08 20:00:05 Franck

在我发布这个问题之前，我也试图做到这一点，但是我没有看到答案，但是如果告诉你我等了太久才能看到结果，那将是一个谎言。这是算法分析类的作业，因此我需要添加clock（）并针对不同的数据大小运行代码（例如1000,10000,100000, ,1000000个输入）。所以我从你的回答中得出的结论是，如果我等待足够长时间，我应该得到一个结果，对吧？ – Valentino

是的，如果你足够长的时间，你应该得到结果。如何在不同的数据大小之间改变你的时间？ 10000的时间应该比1000的时间慢100倍，而100000的时间应该比1000的时间慢10000倍。因此，您应该从1000时间开始为任何数据集推断时间。 – Franck

我尝试了一组1000个数字并得到结果。非常感谢您的时间和帮助！ – Valentino

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

回答

相关问题