2017-01-22 196 views
1

我想使用向量而不是數組使用合併排序方法來排序文本文件。代碼的構建,但是當我運行它時,我的一個向量出現了一個outbounds錯誤。使用向量合併排序C++

具體來說:

for (int k = start; k < end; k++) 
{ 
    if (L.at(x) <= R.at(y)) 
    { 
     v.at(k) = L.at(x);   // out of bounds 
     x++; 
    } 
    else 
    { 
     v.at(k) = R.at(y);   // out of bounds 
     y++; 
    } 

} 

我調整矢量 'V' 但INT K靜止遞增到高。即v的大小將是10,但k也將等於10.我試着改變一些值,但是每次編譯函數最後都沒有排序。我查了各種合併排序的方法,每次我都得到相同的界限錯誤。

編輯:我改變了我的循環,現在它通過我的功能。但他們返回一個空白矢量。打印時,整個'v'向量是空格。

全碼:

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

using namespace std 

vector<string> readFile(string fileName) { 
    /* reads a textfile into vector. Works dandy. */ 
} 

vector<string> merge(vector<string>& v, int start, int mid, int end) { 
    int n1 = mid - start + 1; 
    int n2 = end - mid; 

    vector<string> L; 
    vector<string> R; 

    L.resize(n1 + 1); // size left vector 
    R.resize(n2 + 1); // size right vector 

    for (int i = 1; i < n1; i++) { 
     L.at(i) = v.at(start + i - 1); // populate left vector 
    } 
    for (int j = 1; j < n2; j++) { 
     R.at(j) = v.at(mid + j);  // populate right vector 
    } 

    int x = 1; 
    int y = 1; 

for (int k = start; k < end; k++) 
{ 
    if (L.at(x) <= R.at(y)) 
    { 
     v.at(k) = L.at(x);   // merge left vector into v 
      if (x < L.size() - 1) // prevents x from increasing past bounds of L vector 
      x++; 
    } 
    else 
    { 
     v.at(k) = R.at(y);   // merge right vector into v 
     y++; 
    } 
    return v; 
} 

vector<string> mergeSort(vector<string>& v, int start, int end) { 
    int middle; 
    if (start < end)     // base case 
    { 
     middle = (start + end)/2;  // find middle 
     mergeSort(v, start, middle); // divide vectors 
     mergeSort(v, middle + 1, end); 
     merge(v, start, middle, end); // merge sorted vectors 
    } 
    return v; 
} 

int main() { 
    vector<string> vectorReadIn; 
    vector<string> sortedVector; 
    int x = 0; 

    string fileName = "C:/Users/User/Downloads/Algorithims/Perm Words/perm15k.txt"; 

    vectorReadIn = readFile(fileName); // reads file into vector 

    sortedVector = mergeSort(vectorReadIn, 1, vectorReadIn.size()); // calls mergesort 
    cout << "Sorted file:" << endl; 
    while (x < 8) { 
     cout << sortedVector.at(x); 
     x++; 
    } 
} 
+0

可能的重複[在C++中使用內置函數(或任何其他方法)對二維數組排序?](http://stackoverflow.com/questions/20931669/sort- a-2d-array-in-c-using-built-in-functions或任何其他方法) –

+0

請參閱我的答案:http://stackoverflow.com/a/38249167/2642059你在找什麼'sort(begin(vectorReadIn),end(vectorReadIn))'。 –

+0

我應該澄清,我比較了各種排序算法的時間複雜性,並且我陷入了合併排序。我決定使用矢量,因爲它們可以動態地改變,並且避免使用數組。 –

回答

0

所有索引,你在你的vectors做的是基於1的。 C++矢量(和數組)使用基於0的索引。至少,xy應該初始化爲0,ij填充循環中的索引應從0開始(對循環中的結束條件和用法進行適當更改),並且調用第二個參數mergeSortmain應該是0,而不是1.

+0

我做了修改,並且進一步了一點。我正在離開我的老師的僞代碼模板。她可能在某個地方佔了一席之地,我錯過了它。現在我的載體回來了!我將在上面編輯更多信息。 –