Click here to Skip to main content
14,699,570 members
Please Sign up or sign in to vote.
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
Updated 14-Dec-17 5:04am
v5

We don't know what problems you meet - but looking at that the first thing that springs to mind is this:
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.
   
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?
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.
   
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:
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]
   
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.

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




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900