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

This is a discussion on plzzzzzz... i need a help in natural merge sort within the C++ Programming forums, part of the General Programming Boards category; hello for everyone here well i am a fresh man here ... and i'm really pleased that i'm a member ...

  1. #1
    Registered User sam-j89's Avatar
    Join Date
    May 2009
    Posts
    14

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

    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;
    }
    ************************************************** **************

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Quote Originally Posted by sam-j89 View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    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;
    	}
    }
    1. '/0' should be '\0' as already mentioned.
    2. 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
    3. Not all code paths return a value
    4. 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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User sam-j89's Avatar
    Join Date
    May 2009
    Posts
    14
    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;
    	}
    }

  5. #5
    Registered User sam-j89's Avatar
    Join Date
    May 2009
    Posts
    14
    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);
    }

  6. #6
    Registered User sam-j89's Avatar
    Join Date
    May 2009
    Posts
    14
    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;
    }

  7. #7
    Registered User sam-j89's Avatar
    Join Date
    May 2009
    Posts
    14
    still not working!!!!!!!!!!!!!!1

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    What is the result, and how is it different from what you expect?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User sam-j89's Avatar
    Join Date
    May 2009
    Posts
    14
    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;
    }

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User sam-j89's Avatar
    Join Date
    May 2009
    Posts
    14
    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

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User sam-j89's Avatar
    Join Date
    May 2009
    Posts
    14
    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

  15. #15
    Registered User Kanshu's Avatar
    Join Date
    May 2009
    Posts
    27
    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;
    }

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge Sort Help
    By blindman858 in forum C++ Programming
    Replies: 5
    Last Post: 05-14-2005, 09:47 PM
  2. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  3. merge sort tutorial from cprogramming.com
    By Micko in forum C Programming
    Replies: 0
    Last Post: 03-15-2005, 08:43 AM
  4. Natural Merge Sort
    By penny_731729 in forum C Programming
    Replies: 1
    Last Post: 04-28-2003, 04:12 PM
  5. help with merge sort
    By maloy in forum C Programming
    Replies: 4
    Last Post: 03-04-2002, 05:22 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21