Shell sort won't work in this program (the algorithm itself works just fine)
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 15 of 18

Thread: Shell sort won't work in this program (the algorithm itself works just fine)

Hybrid View

  1. #1
    Join Date
    Feb 2013
    Posts
    11

    Shell sort won't work in this program (the algorithm itself works just fine)

    Code:
    #include <iostream>
    using namespace std;
    
    class CD
    {
    public:
    	static const int num = 100;
    	char publisher[num], title[num], location[num];
    	int year;
    public:
    	void virtual input()=0;
    	void virtual output()=0;
    };
    
    class Classical: public CD
    {
    protected:
    	static const int num = 100;
    	char composer[num], conductor[num];
    public:
    	void virtual input()=0;
    	void virtual output()=0;
    };
    
    class Popular: public CD
    {
    private:
    	static const int num=100;
    	char name_of_the_band[num], composer[num], leading_performer[num];
    public:	
    	void input()
    	{	cout << "\nPublisher        : ";
    	cin >> publisher;
    	cout << "Title            : ";
    	cin >> title;
    	cout << "Location         : ";
    	cin >> location;
    	cout << "Year             : ";
    	cin >> year;
    	cout << "Name of the band : ";
    	cin >> name_of_the_band;
    	cout << "Composer         : ";
    	cin >> composer;
    	cout << "Leading performer: ";
    	cin >> leading_performer;	
    }
    	void output()
    	{
    		cout << "\nPublisher         : " << publisher;
    		cout << "\nTitle             : " << title;
    		cout << "\nLocation          : " << location;
    		cout << "\nYear              : " << year;
    		cout << "\nName of the band  : " << name_of_the_band;
    		cout << "\nComposer          : " << composer;
    		cout << "\nLeading performer : " << leading_performer;
    	}
    };
    
    class Symphony: public Classical
    {
    private:	static const int num=100;
    			char orchestra[num], location[num];
    public:		void input(){
    		cout << "\nPublisher: ";
    		cin >> publisher;
    		cout << "Title    : ";
    		cin >> title;
    		cout << "Location : ";
    		cin >> location;
    		cout << "Year     : ";
    		cin >> year;
    		cout << "Composer : ";
    		cin >> composer;
    		cout << "Conductor: ";
    		cin >> conductor;
    		cout << "Orchestra: ";
    		cin >> orchestra;
    		cout << "Location : ";
    		cin >> location;}
    	void output()
    	{	cout << "\nPublisher         :" << publisher;
    		cout << "\nTitle             :" << title;
    		cout << "\nLocation          :" << location;
    		cout << "\nYear              :" << year;
    		cout << "\nComposer          :" << composer;
    		cout << "\nConductor         :" << conductor;
    		cout << "\nOrchestra         :" << orchestra;
    		cout << "\nLocation          :" << location;}};
    void ShellSort(CD *arr[],int n); //function prototype for our Shell sort algorithm
    
    void main()
    {
    	CD *cdptr[100]; //pointer declaration for each of our class
    	Popular *popptr;
    	Symphony *symptr;
    	int n=0, choose, symphonyCD, popularCD, pop;
    	char terminate;
    
    	cout << "\t\tEnter 2 or more CD-s to sort!" << endl;
    	do // do-while statement which allows the user to enter data and terminate the program when he wants
    	{
    			cout << "\n1.Classical";
    			cout << "\n2.Popular";
    			cout << "\n3.Sort";
    			cout << "\n4.Display";
    			cout << "\n5.Terminate program";
    			cout << endl << endl;
    			cout << "\nChoose category: ";
    			cin>>choose;
    			switch(choose)							//switch for the user to choose the type of input
    			{
    			case 1:
    				cout << "\nChoose category: ";
    				cout << "\n1.Symphony";
    			    cout << endl << endl;
    				cin >> pop;
    				if(pop==1) //if-else statement to chose the type of classical CD
    				{
    					cout << "\nEnter number of symphony cd: ";
    					cin >> symphonyCD;
    					int static b;
    					for(int i=0; i<symphonyCD;i++)
    					{
    						cout << "\nNr. " << ++b << endl;
    						symptr = new Symphony;
    						symptr->input();
    						cdptr[n++]=symptr;
    					}
    				}
    				else
    					cout << "\nNot recognized value!";
    				break;
    			case 2:
    				cout << "\nEnter number of popular cd: ";
    				cin >> popularCD;
    				int static a;
    				for(int i=0; i<popularCD;i++)
    				{
    					cout << "\nNr. " << ++a << endl;
    					popptr = new Popular;
    					popptr->input();
    					cdptr[n++]=popptr;
    				}
    				break;
    			case 3:
    				ShellSort(cdptr,100); //function call statement for our Shell Sort algorithm
    				break;
    			case 4:
    				if(n==0)
    				cout << "\nNo data entered!" << endl;
    				for(int i=0; i<n;i++)
    				{
    					cdptr[i]->output();
    					cout << endl;
    				}
    				break;
    			case 5:
    				cout << "\nDo you want to terminate the program? (y/n)";
    				cin >> terminate;
    				break;
    			default:
    				cout << "\nNot recognized value!" << endl;
    			}
    	}while(terminate!='y');
    	
    	system("pause");
    }
    void ShellSort(CD *arr[],int n)
    {
    	int i,j,increment;
    	CD *temp;
    	for(increment=n/2; increment>0; increment /= 2)
    		{
    			for(i=increment; i<n; i++)
    			{
    				temp=arr[i];
    				for(j=i; j>=increment; j -= increment)
    				{
    					if(temp->title < arr[j-increment]->title)
    					{
    					arr[j] = arr[j-increment];
    					}
    					else break;}
    				arr[j] = temp;}}}

  2. #2
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    1) Your code is not specific to Visual C++. It uses no MFC, no ATL, so it is a generic C++ program. Next time post in the non-Visual C++ forum.

    2) Please reformat your code in a coherent manner. It is very difficult to read with the format as it is now.

    3)
    Code:
    void main()
    The main() function returns int, not void.

    4)
    Code:
    int static b;
    //...
    int static a;
    What is the reason for these static variables? There is no need to write code that uses static variables in the context that you're using them here.

    5)
    Code:
    ShellSort(cdptr,100); //function call statement for our Shell Sort algorithm
    And what would happen if only 10 items are in the array that were inputted instead of 100? You will be sorting 90 pieces of junk data with 10 pieces of good data. That's the main flaw with your function -- that ShellSort doesn't know exactly how many items to really sort.

    Last, did you debug your code using the debugger? Visual C++ comes with one of the best debuggers in the world of C++. Did you use it? You single step through your program, watch variables, check the flow of the program, and then you can see where it goes wrong.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; February 6th, 2013 at 04:26 AM.

  3. #3
    Join Date
    Feb 2013
    Posts
    11

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    Paul thank you for your reply. I am sorry for posting my question on a Visual c++ forum. I corrected what you recommend and yes I did use the Visual c++ debugger. The problem is that the if statement in the algorithm part gives always a false result

  4. #4
    Join Date
    Feb 2013
    Posts
    11

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    Thank you for your reply Paul.
    I am sorry for posting my question int the wrong question. I have tried to debug my program and the problem is that the "if" statement in the sort algorithm is always evaluated as false.

  5. #5
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,098

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    Quote Originally Posted by devilsummer View Post
    Thank you for your reply Paul.
    I am sorry for posting my question int the wrong question. I have tried to debug my program and the problem is that the "if" statement in the sort algorithm is always evaluated as false.
    So, the next step is to look at the values the if statement is looking at, and find out why it's always evaluating false.

  6. #6
    Join Date
    Feb 2013
    Posts
    11

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    I have been doing that, but I dont see any problems

  7. #7
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,098

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    Quote Originally Posted by devilsummer View Post
    I have been doing that, but I dont see any problems
    So you look at this statement

    if(temp->title < arr[j-increment]->title)

    you look at temp->title and arr[j - increment]->title, see that arr[j - increment]->title is less than temp->title and the statement still evaluates to false? I don't believe it.

  8. #8
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,098

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    I'll ask again. Are you saying you look at the two values, lets say the equal 1 and 2, so your if statement is essentially
    if(1 < 2)
    and that's evaluating to false? Again, I don't believe it. Please verify that you're actually examining the values correctly.

  9. #9
    Join Date
    Feb 2013
    Posts
    11

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    I have checked it over and over again. The moment it checks the "if" statement, it goes immediately to the "break" statement (despite the condition). That is why I posted this problem here, because I cant find a solution

  10. #10
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,098

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    Quote Originally Posted by devilsummer View Post
    I have checked it over and over again. The moment it checks the "if" statement, it goes immediately to the "break" statement (despite the condition). That is why I posted this problem here, because I cant find a solution
    That's twice now you've ignored the question I asked you. Are you looking at the variables it's evaluating? Yes or no?

  11. #11
    Join Date
    Feb 2013
    Posts
    11

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    Yes i am.

  12. #12
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,098

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    Quote Originally Posted by devilsummer View Post
    Yes i am.
    And...? If you're saying the if statement is thinking 1 is not less than 2, you're not looking at the variables correctly. The compiler won't make that mistake. A small, complete and compilable example that reproduces the problem would help.

  13. #13
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    Quote Originally Posted by devilsummer View Post
    I have checked it over and over again. The moment it checks the "if" statement, it goes immediately to the "break" statement (despite the condition). That is why I posted this problem here, because I cant find a solution
    The "solution" is to use the right functions to compare arrays, or use std::string to represent strings.
    Code:
    	static const int num = 100;
    	char publisher[num], title[num], location[num];
    Code:
    if(temp->title < arr[j-increment]->title)
    You are comparing pointers in that code, not the contents of a string. That's the price you pay when you use char arrays to represent string data instead of string classes.

    The appropriate function is strcmp to compare character arrays. If instead, you used std::string:
    Code:
    #include <string>
    //...
    std::string publisher, title, location;
    not only would your sort code "work" (you still need to fix it so that it knows the right number of items to sort), you wouldn't need the "100", since a std::string is dynamic.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; February 6th, 2013 at 08:19 AM.

  14. #14
    Join Date
    Feb 2013
    Posts
    11

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    Thank you Paul. I will switch to string and see what happens. I appreciate your help

  15. #15
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Shell sort won't work in this program (the algorithm itself works just fine)

    Quote Originally Posted by devilsummer View Post
    That is why I posted this problem here, because I cant find a solution
    Just in addition -- you wound up using char arrays to represent strings -- once you did that, then you need to know how to use char arrays, and obviously you didn't know how to do this.

    You cannot compare char arrays (or any arrays) using the logical operators <, >, <=, >=, etc. You have to write a loop or call a function that loops over all the elements and determines which item is different in each array. In the case of char arrays, the function is strcmp.

    If you had instead used a std::string, then all of that code you had would have worked, since <, >, <=, >=, etc. are all supported by std::string. The trick is that if you're writing this kind of code, use types that are supported by the operators used in such code.

    Regards,

    Paul McKenzie

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center