-1

Below is my implementation of merge sort in C++. I have taken a small input size just for convenience in debugging. The merge sort code is still not working after rectifying a little mistake which resulted in an std::out_of_range exception being thrown.

#include <iostream>
#include <chrono>
#include <fstream>
#include <vector>

using namespace std;
using namespace std::chrono;

void mergeSort(vector<long>, long, long);
void merge(vector<long>, long, long, long);
void sortf(long);
void print(long);

void print(long n) //prints n random numbers in a file
{
    ofstream of("List.txt");
    long i;
    for (i = 0; i < n; i++)
    {
        long x = rand() % n + 1;
        of << x << endl;
    }
    of.close();
}

void sortf(long x) //calls the merge sort function and sends it array of elements which
{ //were previously stored in the file and outputs sorted values to another file
    vector<long> arr;
    ifstream f("List.txt");
    long i = 0;
    long line;
    while (i < x)
    {
        f >> line;
        arr.push_back(line);
        i++;
    }
    high_resolution_clock::time_point t1 = high_resolution_clock::now();

    long len = arr.size() - 1;
    mergeSort(arr, 0, len); //calls merge sort

    high_resolution_clock::time_point t2 = high_resolution_clock::now();
    auto duration = duration_cast<nanoseconds>(t2 - t1).count();
    cout << "\nTime taken:\n" << duration << " nanoseconds.\n"; //outputs time taken 
    ofstream of("ListOut3.txt");
    for (i = 0; i < x; i++)
    {
        cout << arr.at(i) << endl;
    }
    for (i = 0; i < x; i++)
    {
        of << arr.at(i) << endl;
    }
}

void mergeSort(vector<long> arr, long l, long r)
{
    long n = arr.size();
    if (l >= r) //Base condition to stop recursion
    {
        return;
    }

    long mid = (l + r) / 2; //calculates mid position for partitioning

    mergeSort(arr, l, mid);
    mergeSort(arr, (mid + 1), r);
    merge(arr, l, mid, r);
}

void merge(vector<long> arr, long l, long mid, long r) //applies merging
{
    vector<long> lv;
    vector<long> rv;

    int p;

    for (p = l; p < mid; p++)
    {
        lv.push_back(arr.at(p));
    }
    for (p = mid; p < r; p++)
    {
        rv.push_back(arr.at(p)); //Error Solved
    }

    long l1 = lv.size();
    long l2 = rv.size();

    long i = 0, j = 0, k = 0;

    while (i < l1 && j < l2)
    {
        if (lv.at(i) < rv.at(j))
        {
            arr.at(k) = lv.at(i);
            i++;
        }
        else
        {
            arr.at(k) = rv.at(j);
            j++;
        }
        k++;
    }
    while (i < l1)
    {
        arr.at(k) = lv.at(i);
        k++;
        i++;
    }
    while (j < l2)
    {
        arr.at(k) = rv.at(j);
        k++;
        j++;
    }
}

int main()
{
    long n = 4;
    print(n); //printing n numbers in the file
    sortf(n);
}

The exact output of the program is:

Time taken:
6897 nanoseconds.
4
3
2
4

Please help me figure out the cause since I am new to STL and vectors.

50calrevolver
  • 142
  • 2
  • 13
  • The right tool to solve such problems is your debugger. You should step through your code line-by-line *before* asking on Stack Overflow. For more help, please read [How to debug small programs (by Eric Lippert)](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). At a minimum, you should \[edit] your question to include a [Minimal, Complete, and Verifiable](http://stackoverflow.com/help/mcve) example that reproduces your problem, along with the observations you made in the debugger. – πάντα ῥεῖ Feb 25 '17 at 19:16
  • I have debugged my code line by line. I have also mentioned the exact line where the error is being encountered in the comments. I am just not able to identify the reason behind the error. There is certainly a logical error in my code but I am unable to find it. I need help not with identifying where the error is but by identifying what exactly is causing that particular error at that exact line. – 50calrevolver Feb 25 '17 at 19:21
  • Well, the reason is you have an empty vector at that point. Check why it isn't copied from another one, or not filled in the way you expect it. – πάντα ῥεῖ Feb 25 '17 at 19:23
  • Also, I am unable to figure out that why the message "Encountered!", which is included in my catch block, is being printed twice. – 50calrevolver Feb 25 '17 at 19:26
  • `rv` is obviously an uninitialized, empty vector. Did you mean to initialize it with a certain size like:`vector rv(arr.size);`? – πάντα ῥεῖ Feb 25 '17 at 19:29
  • Okay, sorry for being such foolish, but I just rectified a stupid mistake on my part. I am editing the question code, not answering it, since the merge sort code is still not working. – 50calrevolver Feb 25 '17 at 19:30
  • It's printed twice because you don't quit the program after catching the exception, so that function is executed another time, rising another exception – Bob__ Feb 25 '17 at 19:31
  • I have edited the question. The mistake was a result of forming a bad habit of using arrays for dynamic initialization for quite a few of my assignments over the weekend. Now the code works without any runtime errors, but still the merge sort output is incorrect and I shall try my best to solve it after some debugging! – 50calrevolver Feb 25 '17 at 19:34
  • `mergeSort(arr, 0, len);` is a no-op. All arguments are passed by value. – melpomene Feb 25 '17 at 19:50
  • I believe I will have to pass the vector by reference, so that the changes made in the merge function will get reflected back in the vector passed in the calling function mergeSort. Am I right? What would be the correct way to do that? – 50calrevolver Feb 25 '17 at 19:57
  • Got it working. Passed vector by reference using the syntax mentioned in: http://stackoverflow.com/a/15890794/7395477 . Now the code works flawlessly and in a logically correct manner. – 50calrevolver Feb 25 '17 at 20:18

1 Answers1

1

Changed the code so that the vector was passed by reference. Now it working correctly and giving the desired output. Below is the correct, working solution:

#include <iostream>
#include <cstdlib>
#include <chrono>
#include <fstream>
#include <array>
#include <vector>

using namespace std;
using namespace std::chrono;

void mergeSort(vector<long>&, long, long);
void merge(vector<long>&, long, long, long);
void sortf(long);
void print(long);

void print(long n) //prints n random numbers in a file
{
    ofstream of("List.txt");
    long i;
    for (i = 0; i < n; i++)
    {
        long x = rand() % n + 1;
        of << x << endl;
    }
    of.close();
}

void sortf(long x) //calls the merge sort function and sends it array of elements which
{ //were previously stored in the file and outputs sorted values to another file
    vector<long> arr;
    ifstream f("List.txt");
    long i = 0;
    long line;
    while (i < x)
    {
        f >> line;
        arr.push_back(line);
        i++;
    }
    high_resolution_clock::time_point t1 = high_resolution_clock::now();

    long len = arr.size() - 1;
    mergeSort(arr, 0, len); //calls merge sort

    high_resolution_clock::time_point t2 = high_resolution_clock::now();
    auto duration = duration_cast<nanoseconds>(t2 - t1).count();
    cout << "\nTime taken:\n" << duration << " nanoseconds.\n"; //outputs time taken 
    ofstream of("ListOut3.txt");
    for (i = 0; i < x; i++)
    {
        cout << arr.at(i) << endl;
    }
    for (i = 0; i < x; i++)
    {
        of << arr.at(i) << endl;
    }
}

void mergeSort(vector<long> &arr, long l, long r)
{
    if (l >= r) //Base condition to stop recursion
    {
        return;
    }

    long mid = (l + r) / 2; //calculates mid position for partitioning

    mergeSort(arr, l, mid);
    mergeSort(arr, (mid + 1), r);
    merge(arr, l, mid, r);
}

void merge(vector<long> &arr, long l, long mid, long r) //applies merge sort algorithm
{
    vector<long> lv;
    vector<long> rv;

    int p;
    for (p = l; p <= mid; p++)
    {
        lv.push_back(arr.at(p));
    }
    for (p = mid+1; p <= r; p++)
    {
        rv.push_back(arr.at(p));
    }

    long l1 = lv.size();
    long l2 = rv.size();

    long i = 0, j = 0, k = l;

    while (i < l1 && j < l2)
    {
        if (lv.at(i) < rv.at(j))
        {
            arr.at(k) = lv.at(i);
            i++;
        }
        else
        {
            arr.at(k) = rv.at(j);
            j++;
        }
        k++;
    }
    while (i < l1)
    {
        arr.at(k) = lv.at(i);
        k++;
        i++;
    }
    while (j < l2)
    {
        arr.at(k) = rv.at(j);
        k++;
        j++;
    }
}

int main()
{
    long n = 60;
    print(n); //printing n numbers in the file
    sortf(n);
}
50calrevolver
  • 142
  • 2
  • 13