C++

Forum

 
Problem while doing merge-sorting

herad (12)
Sorry for the long post. I am doing a merge sort with a vector of strings. So far I implemented most of the algorithm in the function.

I take input from the command prompt using <input.txt to pass input to stdin from a text file , and then output using >output.txt.

The text file would look like this (notice the blank line):

Hello
world.

3 days of summer!


For each line of text, it is inserted into a vector , that text is then rotated left and pushed back into the vector, and repeats until n-1. And then I run the merge sort to sort the vector strings and print the output. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
int main(int argc, char** argv) {

		string input;
		while(getline(cin, input)){


	vector<string> v;
                //Shift string to the left by 1 character and add it to the vector
		for(int i=0; i< input.length(); i++)
		{
			v.push_back(input);
			rotate(input.begin(),input.begin()+1,input.end());
		}


		//  Print original vector
		cout << "******original*******"<< endl;
		for (vector<string>::size_type i = 0; i < v.size(); ++i)
		{
				  cout << v[i] << endl;
		}


    		//Do the mergesort
         
    		 mergeSort(v, 0, v.size() - 1);
                
                   //print output
    	   	   cout << "*****sorted******"<< endl;
    	   		for (vector<string>::size_type i = 0; i < v.size(); ++i)
    	   		{
    	   				  cout << v[i] << endl;
    	   		

            }

		} //end while loop
}


1
2
3
4
5
6
7
8
9
10
11
12
13
 
void mergeSort(vector<string> &a, int from, int to)
{
	if (from == to)
	{
		return;
	}
	int mid = (from + to) / 2;
	
	mergeSort(a, from, mid);
	mergeSort(a, mid + 1, to);
	merge(a, from, mid, to);

} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
void merge(vector<string> &a, int from, int mid, int to)
{
	int n = to - from + 1; 
	vector<string> b(n); 
	int i1 = from; 
	int i2 = mid + 1;
	int j = 0; /

	while (i1 <= mid && i2 <= to)
	{
		if (a[i1].compare(a[i2]) < 0)
		{
			b[j] = a[i1];
			i1++;
		}
		else
		{
			b[j] = a[i2];
			i2++;
		}
		j++;
	}

	while (i1 <= mid)
	{
		b[j] = a[i1];
		i1++;
		j++;
	}

	while (i2 <= to)
	{
		b[j] = a[i2];
		i2++;
		j++;
	}

	for (j = 0; j < n; j++)
	{
		a[from + j] = b[j];
	}
}



My expected output should be:

******original*******
Hello
elloH
lloHe
loHel
oHell
******sorted*******
Hello
elloH
lloHe
loHel
oHell
******original*******
world.
orld.w
rld.wo
ld.wor
d.worl
.world
******sorted*******
.world
d.worl
ld.wor
orld.w
rld.wo
world.
******original*******
******sorted*******
******original*******
3 days of summer!
days of summer!3
days of summer!3
ays of summer!3 d
ys of summer!3 da
s of summer!3 day
of summer!3 days
of summer!3 days
f summer!3 days o
summer!3 days of
summer!3 days of
ummer!3 days of s
mmer!3 days of su
mer!3 days of sum
er!3 days of summ
r!3 days of summe
!3 days of summer
******sorted*******
days of summer!3
of summer!3 days
summer!3 days of
!3 days of summer
3 days of summer!
ays of summer!3 d
days of summer!3
er!3 days of summ
f summer!3 days o
mer!3 days of sum
mmer!3 days of su
of summer!3 days
r!3 days of summe
s of summer!3 day
summer!3 days of
ummer!3 days of s
ys of summer!3 da


The problem is, when there is a blank newline in the text file then the sorting stops. This is the output I get:

******original*******
Hello
elloH
lloHe
loHel
oHell
******MERGE SORTED*******
Hello
elloH
lloHe
loHel
oHell
******original*******
world.
orld.w
rld.wo
ld.wor
d.worl
.world
******MERGE SORTED*******
.world
d.worl
ld.wor
orld.w
rld.wo
world.
******original*******


What seems to be wrong?

Last edited on
zapshe (1834)
Well, this is the best time for you to use your debugging tools and figure it out yourself! Going through the logic of someone else's code can be a bit of a hassle. However, at a slight glance I can see you're using getline and then parsing the input unconditionally.

You might want to try something like this within your while(getline(cin, input)):

1
2
3
4
5
 
if (input.empty()) //Check if you took in an empty line
{
	std::cout << "ITS EMPTY";
	continue; //Don't continue the loop, go back and take another line
}



Just a guess though.
Last edited on
Topic archived. No new replies allowed.