plzzzzzz... i need a help in natural merge sort

**sam-j89** · 05-05-2009

hello for everyone here
well i am a fresh man here ... and i'm really pleased that i'm a member here
well .. i made a program in c++ which is all about natural merge sort on files , since i want to sort my file which contains a randolmy generated words (100 , 1000 .... words , according to Nmax value)
so .. i store my data in the file then call the merge sort function
but the problem is that when my data get bigger(i.e. more than 100 words) my program does a partial sorting on'em , and i think i gets into an infinet loop cuz it does not end successfully ....... so i'm really astonished why!! cuz i'm almost sure that my program is bug-free
so please guyz help me ... and thank you in advance

here is my program bros:

************************************************** *************

Code:

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

int Nmax = 1000;

fstream myfile;


bool compare(char w1[6], char w2[6])
{
	for(int i = 0; i<5; i++)
	{
		if (w1[i]>w2[i])
			return true;
		else if (w1[i]<w2[i])
			return false;
		if (w1[i] == '/0')
			return false;
		else if (w1[i] == '/0')
			return true;
	}
}
void assign(char w1[6], char w2[6])
{
	int i = 0;
	while (w1[i]!='\0')
	{
		w2[i] = w1[i];
		i++;
	}
	w2[i] = w1[i];
}


void distribute(fstream& f1, fstream& f2)
{
	char wrd[6] ,w[6];
	int location;
	myfile.read(w,6);
	do
	{
		f1.write(w,6);
		location = f1.tellp();
		assign(w,wrd);
		myfile.read(w,6);
		while ((!myfile.eof())&&(compare(w,wrd)))
		{
			f1.write(w,6);
			assign(w,wrd);
			myfile.read(w,6);
		}
		if (!myfile.eof())
		{
			f2.write(w,6);
			assign(w,wrd);
			myfile.read(w,6);
			while ((!myfile.eof())&&(compare(w,wrd)))
		    {
			    f2.write(w,6);
			    assign(w,wrd);
				myfile.read(w,6);
		    }
		}
	} while(!myfile.eof());
}


int merge(fstream& f1, fstream& f2)
{
	char w1[6], w2[6], wrd[6];
	bool end_sequence ;
	int nb_sequence = 0;
	f1.read(w1,6);
	f2.read(w2,6);
	while ((!f1.eof())&&(!f2.eof()))
	{		
		end_sequence = false;
		do
		{

		if (compare(w2,w1))
		{			   
			   
				myfile.write(w1,6);
				assign(w1,wrd);
				f1.read(w1,6);
				if ((compare(wrd,w1))||(f1.eof()))
				{
		       	    assign(w2,wrd);
		       	    myfile.write(w2,6);
					f2.read(w2,6);
		      	while ((!f2.eof())&&(compare(w2,wrd)))
		        {
			        myfile.write(w2,6);
			        assign(w2,wrd);
					f2.read(w2,6);
			        
		        }
					end_sequence = true;
				} 
					

		}
		else
		{
			 	   myfile.write(w2,6);
				assign(w2,wrd);
				f2.read(w2,6);
				if ((compare(wrd,w2))||(f2.eof()))
				{
		       	    assign(w1,wrd);
					
					myfile.write(w1,6);
					f1.read(w1,6);
					while ((!f1.eof())&&(compare(w1,wrd)))
		        {
			        myfile.write(w1,6);
			        assign(w1,wrd);
					f1.read(w1,6);
			        
		        }
					end_sequence = true;
				}
				
		}
		}while (!end_sequence);
		nb_sequence++;
	}

	while (!f1.eof())
	{
		assign(w1,wrd);
		myfile.write(w1,6);
		f1.read(w1,6);
		while ((!f1.eof())&&(compare(w1,wrd)))
		{
			myfile.write(w1,6);
			assign(w1,wrd);
			f1.read(w1,6);
		}
		nb_sequence++;
	}
	while (!f2.eof())
	{
		assign(w2,wrd);
		myfile.write(w2,6);
		f2.read(w2,6);
		while ((!f2.eof())&&(compare(w2,wrd)))
		{
			myfile.write(w2,6);
			assign(w2,wrd);
			f2.read(w2,6);
		}
		nb_sequence++;
	}

   return nb_sequence;
}


void Natural_mergeSort()
{
	int nb_sequence;
	fstream t1, t2;
	do
	{
		myfile.open("file1.bin", ios::binary|ios::in);
		t1.open("file2.bin", ios::binary|ios::out);
		t2.open("file3.bin", ios::binary|ios::out);
		t1.clear();
		t2.clear();
		
		distribute(t1, t2);
		myfile.close();
		t1.close();
		t2.close();
		myfile.open("file1.bin", ios::binary|ios::out);
			myfile.clear();		
			
		t1.open("file2.bin", ios::binary|ios::in);
		t2.open("file3.bin", ios::binary|ios::in);
		nb_sequence = merge(t1, t2);
        myfile.close();
		t1.close();
		t2.close();
	} while (nb_sequence!=1);
}







int main()
{
    
	myfile.open("file1.bin", ios::binary|ios::out);
	myfile.clear();
    if (!myfile)
		{
		cerr<<"file could not be opened"<<endl;
		exit(1);
		}
	char word[6];
	srand(time(0));
	int j, length, i, Cascii;
	j = 1;
	while (j<= Nmax)
	{
			length = 1+rand()%5;
			for(i=0; i<length; i++)
			{
				Cascii= 97+rand()%25;
				word[i]= char(Cascii);
			}
			word[i] = '\0';
			cout<<word<<endl;
			myfile.write(word,6);
		j++;
	}
	myfile.close();
	cout<<"*************"<<endl;
	Natural_mergeSort();
	myfile.open("file1.bin", ios::binary|ios::in);
	myfile.seekg(0);
	while (!myfile.eof())
	{
		myfile.read(word,6);
		cout<<word<<endl;
	}
    myfile.close();

	return 0;
}

************************************************** **************

**iMalc** · 05-05-2009

Originally Posted by sam-j89

cuz i'm almost sure that my program is bug-free

Code:

		if (w1[i] == '/0')
			return false;
		else if (w1[i] == '/0')
			return true;

Forget trying to be sure your program is bug-free. Without rigorous unit tests your code wont be bug free. And even then...

Those '/0' multicharacter literals are probably supposed to be '\0' for starters, and I noticed that in 5 seconds.
I don't have time to go over this thoroughly, but I'll so that in an hour when I'm back again.

**iMalc** · 05-05-2009

Just to further dispel any speculations as to your code being bug-free, I shall point out the four bugs with this one function alone:

Code:

bool compare(char w1[6], char w2[6])
{
	for(int i = 0; i<5; i++)
	{
		if (w1[i]>w2[i])
			return true;
		else if (w1[i]<w2[i])
			return false;
		if (w1[i] == '/0')
			return false;
		else if (w1[i] == '/0')
			return true;
	}
}

'/0' should be '\0' as already mentioned.
The last 'if' and the following 'else if' are tesing the exact same thing, therefore the second one that returns true can never be hit
Not all code paths return a value
Lack of const-correctness on the input parameters

I would have let you off on the last one if this were the C forum though.
Not to mention, the first two functions are attempting to do the job of functions that are part of std::string, which you should be using. But I'll refrain from going as far as to call that one a bug as well.

A furthur quick glance shows that you're not checking if any of your files were opened successfully either. There's another 8 bugs for you.

You can drop the second "using namespace std;".

Could you fix the indentation for the rest of your program please. Replace tabs with a fixed number of spaces before posting.

**sam-j89** · 05-06-2009

Hi iMalc thanx for your notes about my program, and sorry cuz I said it is a bug-free
I did as you told me and corrected my bugs in the program but that didn't work, it still sort the elements partially and not printing my elements when it finishes… you told me also to use the std::string, I considered that but I discovered that I cannot cuz initially I am randomizing the characters and ,assigning 'em to the array of char, and storing it in the file, so when I wanna read from the file using a String variable , it says that conversion cannot be made between char[] and string !!!
Thank you very much again ..

Code:

bool compare(char w1[6], char w2[6])
{
	for(int i = 0; i<5; i++)
	{
		if (w1[i]>w2[i])
			return true;
		else if (w1[i]<w2[i])
			return false;
		if (w1[i] == '\0')
			return false;
		else if (w2[i] == '\0')
			return true;
	}
}

**sam-j89** · 05-06-2009

i also chech my file that they are opened successfully ..

Code:

void Natural_mergeSort()
{
	int nb_sequence;
	fstream t1, t2;
	do
	{
		myfile.open("file1.bin", ios::binary|ios::in);
		t1.open("file2.bin", ios::binary|ios::out);
		t2.open("file3.bin", ios::binary|ios::out);
		t1.clear();
		t2.clear();
		if (!myfile)
		{
			cerr<<"file1 can not be opened"<<endl;
			exit(1);
		}

		
		distribute(t1, t2);
		myfile.close();
		t1.close();
		t2.close();
		myfile.open("file1.bin", ios::binary|ios::out);
			myfile.clear();		
			
		t1.open("file2.bin", ios::binary|ios::in);
		t2.open("file3.bin", ios::binary|ios::in);
		if (!myfile)
		{
			cerr<<"file2 can not be opened"<<endl;
			exit(1);
		}
		if (!myfile)
		{
			cerr<<"file3 can not be opened"<<endl;
			exit(1);
		}
		nb_sequence = merge(t1, t2);
        myfile.close();
		t1.close();
		t2.close();
	} while (nb_sequence!=1);
}

**sam-j89** · 05-06-2009

hey .. here is my last modification

Code:

#include<iostream>
using namespace std;
#include<fstream>
#include<ctime>
#include<string>

int Nmax = 100;

fstream myfile;


bool compare(char w1[6], char w2[6])
{
	string s1 = w1, s2 = w2;
	if (s1 > s2)
		return true;
	else 
		return false;
}


void distribute(fstream& f1, fstream& f2)
{
	string wrd;
	char w[6];
	myfile.read(w,6);
	do
	{
		f1.write(w,6);
		wrd = w;
		myfile.read(w,6);
		while ((!myfile.eof())&&(w > wrd))
		{
			f1.write(w,6);
			wrd = w;
			myfile.read(w,6);
		}
		if (!myfile.eof())
		{
			f2.write(w,6);
			wrd = w;
			myfile.read(w,6);
			while ((!myfile.eof())&&(w > wrd))
		    {
			    f2.write(w,6);
			    wrd = w;
				myfile.read(w,6);
		    }
		}
	} while(!myfile.eof());
}


int merge(fstream& f1, fstream& f2)
{
	char w1[6], w2[6];
	string wrd;
	bool end_sequence ;
	int nb_sequence = 0;
	f1.read(w1,6);
	f2.read(w2,6);
	while ((!f1.eof())&&(!f2.eof()))
	{		
		end_sequence = false;
		do
		{

		if (compare(w2,w1))
		{			   
			   
				myfile.write(w1,6);
				wrd = w1;
				f1.read(w1,6);
				if (( wrd > w1)||(f1.eof()))
				{
		       	    wrd = w2;
		       	    myfile.write(w2,6);
					f2.read(w2,6);
		      	while ((!f2.eof())&&(w2 > wrd))
		        {
			        myfile.write(w2,6);
			        wrd = w2;
					f2.read(w2,6);
			        
		        }
					end_sequence = true;
				} 
					

		}
		else
		{
			 	   myfile.write(w2,6);
				wrd = w2;
				f2.read(w2,6);
				if ((wrd > w2)||(f2.eof()))
				{
		       	    wrd = w1;
					
					myfile.write(w1,6);
					f1.read(w1,6);
					while ((!f1.eof())&&(w1 > wrd))
		        {
			        myfile.write(w1,6);
			        wrd = w1;
					f1.read(w1,6);
			        
		        }
					end_sequence = true;
				}
				
		}
		}while (!end_sequence);
		nb_sequence++;
	}

	while (!f1.eof())
	{
		wrd = w1;
		myfile.write(w1,6);
		f1.read(w1,6);
		while ((!f1.eof())&&(w1 > wrd))
		{
			myfile.write(w1,6);
			wrd = w1;
			f1.read(w1,6);
		}
		nb_sequence++;
	}
	while (!f2.eof())
	{
		wrd = w2;
		myfile.write(w2,6);
		f2.read(w2,6);
		while ((!f2.eof())&&(w2 > wrd))
		{
			myfile.write(w2,6);
			wrd = w2;
			f2.read(w2,6);
		}
		nb_sequence++;
	}

   return nb_sequence;
}


void Natural_mergeSort()
{
	int nb_sequence;
	fstream t1, t2;
	do
	{
		myfile.open("file1.bin", ios::binary|ios::in);
		t1.open("file2.bin", ios::binary|ios::out);
		t2.open("file3.bin", ios::binary|ios::out);
		t1.clear();
		t2.clear();
		if (!myfile)
		{
			cerr<<"file1 can not be opened"<<endl;
			exit(1);
		}		
		distribute(t1, t2);
		myfile.close();
		t1.close();
		t2.close();
		myfile.open("file1.bin", ios::binary|ios::out);
			myfile.clear();		
			
		t1.open("file2.bin", ios::binary|ios::in);
		t2.open("file3.bin", ios::binary|ios::in);
		if (!t1)
		{
			cerr<<"file2 can not be opened"<<endl;
			exit(1);
		}
		if (!t2)
		{
			cerr<<"file3 can not be opened"<<endl;
			exit(1);
		}
		nb_sequence = merge(t1, t2);
        myfile.close();
		t1.close();
		t2.close();
	} while (nb_sequence!=1);
}

int main()
{
	myfile.open("file1.bin", ios::binary|ios::out);
	myfile.clear();
    if (!myfile)
		{
		cerr<<"file could not be opened"<<endl;
		exit(1);
		}
	char word[6];
	srand(time(0));
	int j, length, i, Cascii;
	j = 1;
	while (j<= Nmax)
	{
			length = 1+rand()%5;
			for(i=0; i<length; i++)
			{
				Cascii= 97+rand()%25;
				word[i] = Cascii;
			}
			word[i] = '\0';
			cout<<word<<endl;
			myfile.write(word,6);
		j++;
	}
	myfile.close();
	cout<<"*************"<<endl;
	Natural_mergeSort();
	myfile.open("file1.bin", ios::binary|ios::in);
	while (!myfile.eof())
	{
		myfile.read(word,6);
		cout<<word<<endl;
	}
    myfile.close();
	return 0;
}

**sam-j89** · 05-06-2009

still not working!!!!!!!!!!!!!!1

**matsp** · 05-06-2009

What is the result, and how is it different from what you expect?

--
Mats

**iMalc** · 05-06-2009

That compare function looks reasonably nice now, well done.

merge and distribute are a little hard to follow though because they're a bit long. Perhaps you could look for some lines of code that are used a few times and put them in their own function to simplify things. For example, something like at least these lines of code:

Code:

		f1.read(w1,6);
		while ((!f1.eof())&&(w1 > wrd))
		{
			myfile.write(w1,6);
			wrd = w1;
			f1.read(w1,6);
		}

You can put that in a function and pass wrd, w1, and f1 as parameters (probably passed by reference). Then if you name that function appropriately and use it in as many places as it makes sense to, your code should look simple enough for anyone to follow and hopefully spot whatever bug you have.

**sam-j89** · 05-07-2009

hey iMal , i reconstructed my code into a "neat" one .. but still not working !!!!!!!!!!!!!!!!!!!

Code:

#include<iostream>
#include<fstream>
#include<ctime>
#include<string>
using namespace std;

int Nmax = 20;
fstream myfile;

bool compare(char w1[6], char w2[6])
{
	string s1 = w1, s2 = w2;
	if (s1 > s2)
		return true;
	else 
		return false;
}

void copy_sequence(fstream& f1,fstream& f2, char w1[6], string w2)
{
	f1.read(w1,6);
		while ((!f1.eof())&&(w1 > w2))
		{
			f2.write(w1,6);
			w2 = w1;
			f1.read(w1,6);
		}
}

void distribute(fstream& f1, fstream& f2)
{
	string wrd;
	char w[6];
	myfile.read(w,6);
	do
	{
		f1.write(w,6);
		wrd = w;
		copy_sequence(myfile,f1,w,wrd);
		if (!myfile.eof())
		{
			f2.write(w,6);
			wrd = w;
            copy_sequence(myfile,f2,w,wrd);
		}
	} while(!myfile.eof());
}

int merge(fstream& f1, fstream& f2)
{
	char w1[6], w2[6];
	string wrd;
	bool end_sequence ;
	int nb_sequence = 0;
	f1.read(w1,6);
	f2.read(w2,6);
	while ((!f1.eof())&&(!f2.eof()))
	{		
		end_sequence = false;
		do
		{
			if (compare(w2,w1))
			{
				myfile.write(w1,6);
				wrd = w1;
				f1.read(w1,6);
				if (( wrd > w1)||(f1.eof()))
				{
					wrd = w2;
					myfile.write(w2,6);
					copy_sequence(f2,myfile,w2,wrd);
					end_sequence = true;
				} 
			}
			else
			{
				myfile.write(w2,6);
				wrd = w2;
				f2.read(w2,6);
				if ((wrd > w2)||(f2.eof()))
				{
					wrd = w1;
					myfile.write(w1,6);
					copy_sequence(f1,myfile,w1,wrd);
					end_sequence = true;
				}
			}
		}while (!end_sequence);
		nb_sequence++;
	}
	while (!f1.eof())
	{
		wrd = w1;
		myfile.write(w1,6);
		copy_sequence(f1,myfile,w1,wrd);
		nb_sequence++;
	}
	while (!f2.eof())
	{
		wrd = w2;
		myfile.write(w2,6);
		copy_sequence(f2,myfile,w2,wrd);
		nb_sequence++;
	}

   return nb_sequence;
}

void Natural_mergeSort()
{
	int nb_sequence;
	fstream t1, t2;
	do
	{
		myfile.open("file1.bin", ios::binary|ios::in);
		t1.open("file2.bin", ios::binary|ios::out);
		t2.open("file3.bin", ios::binary|ios::out);
		t1.clear();
		t2.clear();
		if (!myfile)
		{
			cerr<<"file1 can not be opened"<<endl;
			exit(1);
		}		
		distribute(t1, t2);
		myfile.close();
		t1.close();
		t2.close();
		myfile.open("file1.bin", ios::binary|ios::out);
			myfile.clear();				
		t1.open("file2.bin", ios::binary|ios::in);
		t2.open("file3.bin", ios::binary|ios::in);
		if (!t1)
		{
			cerr<<"file2 can not be opened"<<endl;
			exit(1);
		}
		if (!t2)
		{
			cerr<<"file3 can not be opened"<<endl;
			exit(1);
		}
		nb_sequence = merge(t1, t2);
        myfile.close();
		t1.close();
		t2.close();
	} while (nb_sequence!=1);
}

int main()
{
	myfile.open("file1.bin", ios::binary|ios::out);
	myfile.clear();
    if (!myfile)
		{
		cerr<<"file could not be opened"<<endl;
		exit(1);
		}
	char word[6];
	srand(time(0));
	int j, length, i, Cascii;
	j = 1;
	while (j<= Nmax)
	{
		length = 1+rand()%5;
		for(i=0; i<length; i++)
		{
			Cascii= 97+rand()%25;
			word[i] = Cascii;
		}
		word[i] = '\0';
		cout<<word<<endl;
		myfile.write(word,6);
		j++;
	}
	myfile.close();
	cout<<"*************"<<endl;
	Natural_mergeSort();
	myfile.open("file1.bin", ios::binary|ios::in);
	while (!myfile.eof())
	{
		myfile.read(word,6);
		cout<<word<<endl;
	}
    myfile.close();
	return 0;
}

**iMalc** · 05-07-2009

Good, the code looks a little easier to follow like that, but it did unfortunately introduce one litle bug:

Code:

void copy_sequence(fstream& f1,fstream& f2, char w1[6], string w2)

w2 needs to be pass-by-reference here. Otherwise w2 = w1; wont do anything to the variable passed in.
Could you give a better description that "Not working" please. That could mean a million different things. Does the program start? Does it get stuck in an infinite loop? Does it output garbage? Does it output the items in a slightly wrong order? Does it output the items in backwards order? Does it take too long? Does it cause an access violation and terminate?

I don't have time to run the whole program at the moment, but maybe after work. Many of us rely on a good description of what happens to resolve the bug rather than actually running it.

**sam-j89** · 05-08-2009

hii bro iMalc.. here is a description of what happens to my program:
when it finishes randomizing words (i print the randomized words so i can see 'em before storing in the file) it should sort all the words strored in my file and then prints them all sorted ascending.. but the problem is that my program stops at a step i don't know what is it(but i think in the sorting step) , and this "not knowing" is because debugging a program, which sorts 100 words or more to know where the bug is, is impossible . and as a result to this bug, it does not print any word in the file..
well after i terminate my program by closing it .. i go to the created binary file in oreder to see what happened (i open it with notepad), i see that it has been sorted partiallly (i.e. in case of 1000, every chunk of 100 or 150 words has been sorted alone)
thank you agian bro for taking your time

**iMalc** · 05-08-2009

Okay I've had a good look through the code and I can see one likely problem.
My guess is that the do while (!end_sequence) loop is going into an infinite loop. This would happen if the program never goes into the if statements that set end_sequence to true, which happens if wrd is not greater than w1 or w2 and neither file is at eof.
You need more practice at explaining what happens though. Programs don't really just 'stop'. They tend to either crash or go into an infinite loop. Maybe you just didn't know what to call it. Either should be easy to debug especially if you are using a small enough amount of data.

For example, try decreasing Nmax to the smallest possible value that causes the program to not work. Start even as low as 1, and if that doesn't work proplerly, then it will be really easy to step through the code one line at a time until you see what it does wrong.
If it works with 1, then try 2, then 3 etc. Run each a couple of times to be sure.
Lets say you get up to 5 and then it doesn't sort properly sometimes. note down the starting order of the words that failed and then temporarily comment out the code that generates random words and instead put in code to hard-code just those 5 words. Then you will have something that fails every time. Now step through the code one line at a time. Learn the difference between step-over and step-into. You may wish to step over calls to compare for example.

Note that it can even be a good idea to make sure that it works with zero items too! Quite often in the real world the container of data to sort is empty, and using a do while rather than a while in certain places can lead to code that wont work in such a case.

If you're under a lot of time pressure then I'll fire it up in Visual Studio next. For the moment though, I'm hoping I can help enhance your skills such that you are capable of solving more issues on your own, which is all good.

**sam-j89** · 05-09-2009

hi iMalc , well i did my best trying to know what the hell is wrong with my program, but i couldn't figure out the bug that , most likely, gets my program into an infinite loop.
i tried Nmax up to 90 elements, in most cases it did not cause any problem, but when Nmax gets bigger , my program does not give any results ..
i figured out a thing why my program is "chunkly" sorted.. cuz when it gets into an infinite loop, it would have done some sorting stages(merge and distribute) so in a step i dunno what it is it goes infinitely.
one more thing .. when i terminate the program and go to where my 3 files located i see a thing... sometimes i see that file1 is empy and the other two files are not(it could be an indicator that the infinity occures in the merging phase), and sometimes i see that file2 and file3 are empty while file1 is not!(it could be an indicator that the infinity occures in the distributing phase)..
this is all i can say about my program .. soo thanks again for your effort bro

**Kanshu** · 05-09-2009

I ran your program to see the contents of the file and discovered that using !myfile.eof() will read the last record twice. So, if you are using this condition during the merge, it will most likely cause problems.

Code:

while (!myfile.eof())
{
	myfile.read(word,6);
	cout<<word<<endl;
}

Thread: plzzzzzz... i need a help in natural merge sort

Thread Tools

Search Thread

Display

plzzzzzz... i need a help in natural merge sort

Similar Threads

Merge Sort Help

threaded merge sort

merge sort tutorial from cprogramming.com

Natural Merge Sort

help with merge sort