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;}}}
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)
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
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
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.
Re: Shell sort won't work in this program (the algorithm itself works just fine)
Quote:
Originally Posted by
devilsummer
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.
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
Re: Shell sort won't work in this program (the algorithm itself works just fine)
Quote:
Originally Posted by
devilsummer
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.
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;
}
}
}
}
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.
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
Re: Shell sort won't work in this program (the algorithm itself works just fine)
Quote:
Originally Posted by
devilsummer
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?
Re: Shell sort won't work in this program (the algorithm itself works just fine)
Re: Shell sort won't work in this program (the algorithm itself works just fine)
Quote:
Originally Posted by
devilsummer
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.
Re: Shell sort won't work in this program (the algorithm itself works just fine)
Quote:
Originally Posted by
devilsummer
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
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)
Re: Shell sort won't work in this program (the algorithm itself works just fine)
Quote:
Originally Posted by
devilsummer
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
Re: Shell sort won't work in this program (the algorithm itself works just fine)
Quote:
Originally Posted by
devilsummer
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)
I still don't think it works fine, since you're sorting garbage data if you have less than 100 items. You can't sort invalid, uninitialized data with good data.
That last parameter to ShellSort() must be the exact number of valid items in the array to sort, not 100.
Regards,
Paul McKenzie
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
