Make it faster

[NOSgraf]

Write your question here.
So my program is ready and it works just fine but im sending it to our site of the university and it doesn't accept my solution because it works longer than 1 sec. (>1.000) any ideas about how can i make my program faster?

  #include <iostream>
#include <vector>
#include <fstream>
using namespace std;

int main()
{
    vector<int> myvector;
    vector<int> myvector2;
    int N, M;
    ifstream dat;
    ofstream sol;
    dat.open("merge.dat");
    dat >> N;
    int myint;
    for ( int  i = 0; i < N; i++){
            dat >> myint;
       myvector.push_back(myint);
    }
    dat >> M;
    for ( int  i = 0; i < M; i++){
        dat >> myint;
        myvector2.push_back(myint);
    }
    dat.close();
    for ( int  i = 0; i < M; i++){
        myvector.push_back(myvector2[i]);
    }
    for ( int  i = 0; i < myvector.size(); i++){
        for ( int  j = 0; j < myvector.size(); j++){
                if ( myvector[i] > myvector[j]){
            swap(myvector[i], myvector[j]);
                }
        }
    }
    sol.open("merge.sol");
    for ( int  i = 0; i < myvector.size(); i++){
        sol << myvector[i] << endl;
    }
    sol.close();
    return 0;
}

[Nico]

What does the data in "merge.dat" look like? Without it it is very hard to test the code.

In general: to speed things up: try to get rid of (nested) loops where possible.

You may also reconsider your use if the swap-function.
http://www.cplusplus.com/reference/algorithm/swap/
http://www.cplusplus.com/reference/algorithm/sort/

I don't know if myvector and myvector2 are ensured to be sorted, but if they are not it might also help to sort them first individually (and subsequently reconsidering the need for nested loops).

Kind regards, Nico

[Repeater]

Why do you have two vectors if all you do is copy one onto the end of the other?

Remove myvector2. Set myvector to the right size at the start (resizing vectors is expensive). Load all the values into one vector to begin with.

I see you're sorting the vector of int values using what is widely regarded as a very, very slow sort algorithm. Is that compulsory, or can you use a better algorithm?

[JLBorges]

> any ideas about how can i make my program faster?

What is the problem statement? (What is your program expected to do?)

[NOSgraf]

Well inside the merge.dat i have two vectors,arrays or whatever you want to do this exercise with so i chose vectors. So my vector2 is necessary because my exercise demands it and then i have to combine them and output all of this from the biggest to the smallest element but the problem is it takes more than 1.000
merge.dat looks like this example:
input:
5
10 7 7 3 2
4
9 8 7 1
output:
10
9
8
7
7
7
3
2
1

[Repeater]

Does it explicitly tell you what sorting algorithm to use, or could you use one that doesn't take so long?

The data you have in each file is ALREADY SORTED. This is a massive clue for the best way to create the output.

This exercise is clearly meant to make you think about how to do this efficiently. This is programming; thinking about the best way to solve the problem.

How would you do this ON PAPER? Here are the inputs:

10 7 7 3 2

9 8 7 1

Now write a new set of that data, sorted. What do you write down first? 10. Then what? 9. How did you know which to write first? How did you know which to write second?

Cross out the ones you've already copied as you go. The algorithm is very simple and very obvious once you've thought about it. Seriously, solve this on paper first.

[NOSgraf]

The text file merge.dat contains four lines. The first line contains the natural number N (1 ≤ N ≤ 100 000) - the number of dubolomas in the first line.

The second line contains N positive integers written through a space. The numbers go in non-increasing order. Each number lies in the range from 1 to 1 000 000 000.

The third line contains the natural number M (1 ≤ M ≤ 100 000) - the number of dubolomas in the second rank.

The fourth line contains M natural numbers written through a space. The numbers go in non-increasing order. Each number lies in the range from 1 to 1 000 000 000.
This is what it says , there are some weird words but don;t pay attention to them i just translated it

[Repeater]

There must be more to the exercise; that description you gave us doesn't say anything about reading numbers or sorting them or writing them or anything for you to actually do.

[NOSgraf]

Corporal Arum faced an unsolvable task for him. Before him there are two rows of wooden soldiers Oorfene Dzhusa (dubolom), in each of them the dabolomes are arranged according to the growth (from the highest to the lowest). Corporal need to build dubolomas in one line but so that they are again located in the growth from the highest to the lowest.

Help Corporal Arum solve this problem.

The input file format is merge.dat

The text file merge.dat contains four lines. The first line contains the natural number N (1 ≤ N ≤ 100 000) - the number of dubolomas in the first line.

The second line contains N positive integers written through a space. The numbers go in non-increasing order. Each number lies in the range from 1 to 1 000 000 000.

The third line contains the natural number M (1 ≤ M ≤ 100 000) - the number of dubolomas in the second rank.

The fourth line contains M natural numbers written through a space. The numbers go in non-increasing order. Each number lies in the range from 1 to 1 000 000 000.

Output file format merge.sol

The text file merge.sol must contain N + M numbers that go in non-incremental order. Each number is the growth of the corresponding daboloma from the first or second rank. Each number should be displayed in a separate line.



This is all it says. So by seing the example i thought he wants two vectors which are already sorted but he wants me to combine them and sort them again .

[Repeater]

Yes. Read each set of numbers into a vector. Given that you know in advance how many you're going to read, make each of these vectors the right size before you start filling them.

Then copy them, in the correct final order, into a third vector (which you also made the correct size at the start). Because they are already sorted in each vector, this is very easy and simple.

Do NOT put them all into a vector together and then start sorting them. When you did the simple example above on paper, you saw what the simple algorithm is.

[JLBorges]

Since in both vectors, "The numbers go in non-increasing order", they are already sorted.
We can directly merge them as they are.

Something along these lines, perhaps (caveat:untested):

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <functional>
#include <iterator>

int main()
{
    std::vector< long long > first, second ;

    {
        // read input into the two vectors
        std::ifstream file( "merge.dat" ) ;

        std::size_t n ;
        file >> n ; // number of integers in the next line
        first.resize(n) ; // make space for 'n' integrs

        // http://www.stroustrup.com/C++11FAQ.html#for
        for( auto& v : first ) file >> v ; // read n numbers into the first vector

        std::size_t m ;
        file >> m ; // number of integers in the next line
        second.resize(m) ; // make space for 'm' integrs
        for( auto& v : second ) file >> v ; // read m numbers into the second vector
    }

    {
        // vectors first and second contain numbers in non-decreasing order
        // (numbers sorted in descending order).
        // merge the numbers in first and second and write the merged sequence
        // into the output file
        
        std::ofstream file( "merged.sol" ) ; // open the file for output

        // create an iterator to write the merged numbers into the file
        // with a new line after each number
        // http://en.cppreference.com/w/cpp/iterator/ostream_iterator
        std::ostream_iterator< long long > output_iterator( file, "\n" ) ;

        // merge the sequences, and send the output to the file (via the iterator)
        // http://en.cppreference.com/w/cpp/algorithm/merge
        std::merge( first.begin(), first.end(), // first input range
                    second.begin(), second.end(), // second input range
                    output_iterator, // destination to write the merged sequence
                    std::greater<>{} ) ; // a greater number is before a lesser number
                    // http://en.cppreference.com/w/cpp/utility/functional/greater
    }
}