Merge Sort mit Vektoren C++

Question

Ich versuche, eine Textdatei mit dem Merge-Sort-Methode mit Vektoren anstelle von Arrays zu sortieren. Der Code wird erstellt, aber wenn ich ihn ausführe, erhalte ich einen Fehler, der auf einen meiner Vektoren hinausläuft.

Im Einzelnen:

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++; 
    } 

} 

ich die Größe Vektor 'v' noch int K erhöht noch zu hoch. h. die Größe von v wird 10 sein, aber k wird auch gleich 10. Ich habe versucht, einige Werte zu ändern, aber jedes Mal, wenn die Funktion kompiliert wird, endet die Sortierung nicht. Ich habe verschiedene Methoden der Merge-Sortierung nachgeschaut und jedes Mal, wenn ich denselben Fehler außerhalb der Grenzen erhalte.

EDIT: Ich machte eine Änderung an meinen Schleifen, jetzt geht es durch meine Funktionen. Aber sie geben einen leeren Vektor zurück. Der gesamte 'v' Vektor ist Leerzeichen, wenn ich es drucke.

Voll Code:

#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++; 
    } 
} 

Answer 1

die alle Indizierung, die Sie auf Ihre vectors tun ist 1-basiert. C++ - Vektoren (und Arrays) verwenden 0-basierte Indizierung. Zumindest x und y sollten auf 0 initialisiert werden, die Indexierung in den i und j Populationsschleifen sollte bei 0 beginnen (mit entsprechenden Änderungen an der Endbedingung und der Verwendung innerhalb der Schleife), und der zweite Parameter im Aufruf an mergeSort in main sollte 0 sein, nicht 1.