插入和合並排序不適用於大數據集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++

回答

相關問題