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
Page 1 of 2 12 LastLast
Results 1 to 15 of 18

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

  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,429

    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,106

    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,106

    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
    Join Date
    Feb 2013
    Posts
    11

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

    You can try and implement the code yourself. It always evaluates to false. I even tried another form of shell sort algorithm and with this new form it evaluates to true.
    Here is the second algorithm that I used

    Code:
    void ShellSort(CD *array[],int length)
    {
    	CD *tmp;
    	int d;
    	d = length;
    	int flag = 1;
    	while ( flag || (d > 1))
    	{
    		flag = 0;
    		d = (d + 1)/2;
    		for (int i =0; i < (length - d); i++)
    		{
    			if (array[i + d] > array[i])
    			{
    				tmp = array[i+d];
    				array[i + d] = array[i];
    				array[i] = tmp;
    				flag = 0;
    			}
    		}
    	}
    }

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

    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.

  10. #10
    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

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

    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?

  12. #12
    Join Date
    Feb 2013
    Posts
    11

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

    Yes i am.

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

    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.

  14. #14
    Join Date
    Apr 1999
    Posts
    27,429

    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.

  15. #15
    Join Date
    Feb 2013
    Posts
    11

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

    What you say is perfectly logical. I implemented the algorithm in a simple program and it works just fine. When I implement it in the code above with the same values as in the simple program it wont do anything (it doesn't sort the values)

Page 1 of 2 12 LastLast

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