I'm trying to sort a text file using the merge sort method using vectors instead of arrays. The code builds but when I run it I get a an out bounds error on one of my vectors.
Specifically :
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++;
}
}
I resize vector 'v' yet int K still increments to high. i.e. the size of v will be 10, yet k will also equal 10. I've tried changing some values, but every time it compiles the function ends up not sorting. I've looked up various methods of merge sort and each time I keep getting the same out of bounds error.
EDIT: I made a change to my loops, now it goes through my functions. But they return a blank vector. The entire 'v' vector is whitespace when I print it.
Full 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++;
}
}
