Counting inversion [getting wrong answer]

Question

1.00/5 (1 vote)

See more:

A file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated.

Task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.

What I have tried:

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

using namespace std;

void sort(vector<int>& input1, vector<int>& input2, int& inv) {

int temp=0, j=0, temp2=0, z=0;

for(int k=0; k<input1.size(); k++) {
	while (input1[k] > input1[j+1]) {
		temp = input1[k];
		input1[k] = input1[j+1];
		input1[j+1] = temp;
		inv++;
	}
}

for(int p=0; p<input2.size(); p++) {
	
	while (input2[p] > input2[z+1]) {
		temp2 = input2[p];
		input2[p] = input2[z+1];
		input2[z+1] = temp2;
		inv++;
	}
}

for(int o=0; o<input1.size(); o++) {

		if(input1[o] > input2[o]) {
			inv++;
		}
}

cout << "Total inversions are  " << inv;
};


int main(void) {

int count=0;

vector<int> big;
vector<int> one;
vector<int> two;


ifstream inFile;

inFile.open("w2.txt");

if (!inFile) {
	cout << "Unable to open file datafile.txt";	
}

int value;

while(inFile >> value) {
	big.push_back(value);
}


for(int i=0; i<big.size()/2; i++) {
	one.push_back(big[i]);
}
	
	for(int j=big.size()/2; j<big.size(); j++) {
		two.push_back(big[j]);
	}

sort(one, two, count);

}

Posted 13-Dec-17 23:55pm

Member 13575891

Updated 14-Dec-17 4:04am

v5

Add a Solution

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Answer 1 · 2017-12-14T00:10:00

Solution 1

We don't know what problems you meet - but looking at that the first thing that springs to mind is this:

C++

for(int k=0; k<=input1.size(); k++) {
	while (input1[k] > input1[j+1]) {

Since indexes start at zero, if you have n items in input1, you will access elements at indexes
0, 1, 2, ... n - 1, n
So if you have three items, your indexes will be:

k = 0
k = 1
k = 2
k = 3

Which is clearly wrong.

Posted 14-Dec-17 0:10am

OriginalGriff

Comments

Member 13575891 14-Dec-17 6:35am

I got you. It's wrong. but It won't help if I remove equality in the loop. I am still getting the same answer.

But I think it shall give me a segmentation fault? isn't it?

Patrice T · Answer 2 · 2017-12-14T00:29:00

There is a tool that allow you to see what your code is doing, its name is debugger. It is also a great learning tool because it show you reality and you can see which expectation match reality.
When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.

Jochen Arndt · Answer 3 · 2017-12-14T00:32:00

Solution 3

With C/C++ arrays use zero based indexes. As a result, valid indexes for non-empty arrays are from 0 to the size minus one. But you are using loops which run up to and including the size. This might move undefined values into your vectors.

So you have to use

for(int k = 0; k < input1.size(); k++) {

instead and similar for the other loop.

Because you are going to swap values checking one item beyond, you ~~can~~ must reduce the number of loops by one. You must also re-initialise the indexes of the next items within the loops instead of re-using them:

for(int k = 0; k < input1.size() - 1; k++) {
    // Start at next item
    int j = k + 1;
    while (input1[k] > input1[j]) {
        // Swap here using j instead of j+1
    }
}

I'm also not sure if incrementing inv within all loops is what you want.

[EDIT]
If you want to calculate the inversion of a vector, I suggest to create a function just for that without sorting:

C++

int GetInversion(const vector<int>& v)
{
    int inv = 0;
    for (int i = 0; i < v.size() - 1; i++)
        for (int j = i + 1; j < v.size(); j++)
            if (v[i] > v[j])
                inv++;
    return inv;
}

[/EDIT]

Posted 14-Dec-17 0:32am

Jochen Arndt

Updated 14-Dec-17 1:08am

v3

Comments

Member 13575891 14-Dec-17 6:43am

why for(int k = 0; k < input1.size() - 1; k++) this ??

why do I go to n-1? I have removed the equality though but my answer is same.

I am wondering that my answer changed when I replaced j+1 with j using int j = k + 1;

I have no idea how this is happening. It should produce the same answer but I am getting different.

Initially I was getting 123503 and now it's 912619

Jochen Arndt 14-Dec-17 6:54am

In your code j is initialised with zero and then only incremented. As a result, j may already reach the array size while there are still more loop runs to be done. Therefore, it must be initialised within the loop for each run.

Because the lower indexes has been already sorted, j must not be set to zero but can be set to the current loop count k. But you want to compare with the next item. So it can be set to k+1. But it must be also ensured that you did not access an item beyond the array size (k+1 < size). That can be done by reducing the loop count by one as mentioned in my solution.

Member 13575891 14-Dec-17 6:47am

Incrementing inv will give me the count of inversion right?

Jochen Arndt 14-Dec-17 7:01am

Basically, yes. But it is usually counted for a single array / vector and not for multiple ones.

You are also counting and sorting within one loop. As a result, you will probably get a wrong result.

I will update my answer.

Member 13575891 14-Dec-17 7:18am

how will you sum up total inversions as the array is first getting divided into two and being sorted recursively, then being merged again to get final sorted array.

so that makes three functions to be computed: f1(sort) + f2(sort) + f3(merge)

Jochen Arndt 14-Dec-17 7:33am

I can't answer that because I don't know what (and why) you are doing it that way. An inversion is calculated for a single array and will be zero after sorting. If all you want is a total value, just get the counts for each array before sorting and sum them up.

Member 13575891 14-Dec-17 7:31am

Is this what you meant to say? correct me please

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

using namespace std;

void GetInversion(vector<int>& v1, vector<int>& v2, vector<int>& v, int& inv) {

for (int i = 0; i < v1.size() - 1; i++)
for (int j = i + 1; j < v1.size(); j++)
if (v1[i] > v1[j])
inv++;

GetInversion2(vector<int> v1, vector<int>& v2, vector<int>& v, int inv);
};

void GetInversion2(vector<int>& v1, vector<int>& v2, vector<int>& v, int& inv2) {

for (int i = 0; i < v2.size() - 1; i++)
for (int j = i + 1; j < v2.size(); j++)
if (v2[i] > v2[j])
inv2++;

for(int o=0; o<v.size()/2; o++) {

if(v[o] > v[o]) {
inv2++;
}
}

cout << "Total inversions are " << inv2;
};

int main(void) {

int count=0;

vector<int> big;
vector<int> one;
vector<int> two;

ifstream inFile;

inFile.open("w2.txt");

if (!inFile) {
cout << "Unable to open file datafile.txt";
}

int value;

while(inFile >> value) {
big.push_back(value);
}

for(int i=0; i<big.size()/2; i++) {
one.push_back(big[i]);
}

for(int j=big.size()/2; j<big.size(); j++) {
two.push_back(big[j]);
}

GetInversion(one, two, big, count);

}

Jochen Arndt 14-Dec-17 7:37am

No. Just call GetInversion() for each array before sorting it:

int invBig = GetInversion(big);
int invOne = GetInversion(one);
int invTwo = GetInversion(two);
// Sort now

Member 13575891 14-Dec-17 9:15am

I have updated the question if it makes you more clear.
The thing is the array big is not meant to be sorted but merged from two array ie one and two by comparisons.

Jochen Arndt 14-Dec-17 9:27am

"Task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array."

So why do you create two arrays, sort them, and merge them?

Member 13575891 14-Dec-17 9:52am

to make it run in nlogn time as per merge sort.
big is the array read from file and rest two are the break of big.

sorting the two break recursively and then storing it in the new array, by comparison, gives me the total inversions.

Jochen Arndt 14-Dec-17 10:24am

I don't think that your total inversion will be the same as the one for the intial (big) array. Especially when performing sorting (which makes the whole operation much slower).

Member 13575891 14-Dec-17 10:04am

check my new updated wrong solution in question.

Member 13575891 14-Dec-17 9:59am

and putting j = k+1 wont work. It doesn't make sense.

Jochen Arndt 14-Dec-17 10:30am

It makes sense. Have a look at my GetInversion() function which works similar. If you search the web, you will find similar - if not identical - code.

I think I will stop here because I and others have shown you some basic mistakes in your code. If you are going to solve the problem in a more complicated way as necessary I wish you good luck.