Sorting parallel arrays in C++
Hello codeguru family,
I am a student and my professor gave our a class a programming project where we declare two arrays, a sting array containing the names of the boroughs and an int array which which holds accident number for each borough. The main function calls getNumAccidents() function to fill the array. it then calls findLowest() to learn which borough had the fewest accidents. It should print out the accident numbers for each borough and then out the borough and accident number with the fewest accidents.
I'm able to get the program to kind of work. When I run it everything works fine but I am not able to get the arrays to sort and match up correctly..
Please look at the code below. and remember I still pretty new at this..
#include<iostream>
#include<iomanip>
#include<string>
#include<cstring>
using namespace std;
class combineSort
{
public:
combineSort()
{
borough[0]="New York City";
borough[1]="Bronx";
borough[2]="Queens";
borough[3]="Brooklyn";
borough[4]="Manhattan";
}
string borough[5];
int accident;
int temp;
};
const int SIZE = 5;
int getNumAccidents(combineSort[], combineSort[]);
int findLowest(combineSort[],combineSort[]);
/*********main*******/
int main()
{
combineSort custom[SIZE];
int j;
getNumAccidents(custom, custom);
findLowest(custom,custom);
return 0;
}
int getNumAccidents(combineSort[], combineSort custom[])
{
{ //New York City
cout<<"\nEnter Number of Accidents for "<<*(custom[0].borough)<<endl;
cin>>custom[0].accident;
if(custom[0].accident<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
//Borough of the Bronx
cout<<"\nEnter Number of Accidents for "<<*(custom[0].borough+1)<<endl;
cin>>custom[1].accident;
if(custom[1].accident<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
//Borough of Queens
cout<<"\nEnter Number of Accidents for "<<*(custom[0].borough+2)<<endl;
cin>>custom[2].accident;
if(custom[2].accident<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
//Borough of Brooklyn
cout<<"\nEnter Number of Accidents for "<<*(custom[0].borough+3)<<endl;
cin>>custom[3].accident;
if(custom[3].accident<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
//Borough of Manhattan
cout<<"\nEnter Number of Accidents for "<<*(custom[0].borough+4)<<endl;
cin>>custom[4].accident;
if(custom[4].accident<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
}
}
//sort to find the lowest accident
int findLowest(combineSort custom[],combinesort custom[])
{
int temp;
for(int i=0;i<5;i++){
if(custom[i].accident<custom[0].accident){
custom[i].temp=custom[i].accident&&*(custom[i].borough);
accident&&*(custom[i].borough)=accident&&*(custom[i].borough);
accident&&*(custom[i].borough)=custom[i].temp;
}
}
cout<<"The lowest number of accident is: "<<custom[0].accident<<endl;
cout<<"In the Borough of: "<<*custom[0].borough<<endl;
return 0;
}
Re: Sorting parallel arrays in C++
I actually posted the wrong code... this one works........ sorry about that......
#include<iostream>
#include<iomanip>
#include<string>
#include<cstring>
using namespace std;
class combineSort
{
public:
combineSort()
{
borough[0]="New York City";
borough[1]="Bronx";
borough[2]="Queens";
borough[3]="Brooklyn";
borough[4]="Manhattan";
}
string borough[5];
int accident;
int temp;
};
const int SIZE = 5;
int getNumAccidents(combineSort[], combineSort[]);
int findLowest(combineSort[]);
/*********main*******/
int main()
{
combineSort custom[SIZE];
int j;
getNumAccidents(custom, custom);
findLowest(custom);
return 0;
}
int getNumAccidents(combineSort[], combineSort custom[])
{
{ //New York City
cout<<"\nEnter Number of Accidents for "<<*(custom[0].borough)<<endl;
cin>>custom[0].accident;
if(custom[0].accident<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
//Borough of the Bronx
cout<<"\nEnter Number of Accidents for "<<*(custom[0].borough+1)<<endl;
cin>>custom[1].accident;
if(custom[1].accident<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
//Borough of Queens
cout<<"\nEnter Number of Accidents for "<<*(custom[0].borough+2)<<endl;
cin>>custom[2].accident;
if(custom[2].accident<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
//Borough of Brooklyn
cout<<"\nEnter Number of Accidents for "<<*(custom[0].borough+3)<<endl;
cin>>custom[3].accident;
if(custom[3].accident<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
//Borough of Manhattan
cout<<"\nEnter Number of Accidents for "<<*(custom[0].borough+4)<<endl;
cin>>custom[4].accident;
if(custom[4].accident<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
}
}
//sort to find the lowest accident
int findLowest(combineSort custom[])
{
int temp;
for(int i=0;i<5;i++){
if(custom[i].accident<custom[0].accident){
custom[i].temp=custom[i].accident;
custom[i].accident=custom[0].accident;
custom[0].accident=custom[i].temp;
}
}
cout<<"The lowest number of accident is: "<<custom[0].accident<<endl;
cout<<"In the Borough of: "<<*custom[0].borough<<endl;
return 0;
}
Re: Sorting parallel arrays in C++
Quote:
Originally Posted by
gwiz01
I actually posted the wrong code... this one works........ sorry about that......
Next time please use Code tags when posting code snippets.
Otherwise your code becomes absolutely unreadable!
Re: Sorting parallel arrays in C++
I hope the point of the exercise was to demonstrate what a pain parallel arrays are and how buggy they can be. If he's suggesting you write code that way, you need a new instructor.
Re: Sorting parallel arrays in C++
Quote:
this one works.......
I'm able to get the program to kind of work. When I run it everything works fine but I am not able to get the arrays to sort and match up correctly..
so it doesn't work fine :confused:
As Victor stated in his post #3, please use code tags. Go Advanced, select the formatted code and click '#'.
There are several isues with this code and I agree with GCDEF in his post #14 re needing a new instructor if this is how he's suggesting you write this code.
Starting with the class
Code:
class combineSort
{
public:
combineSort()
{
borough[0]="New York City";
borough[1]="Bronx";
borough[2]="Queens";
borough[3]="Brooklyn";
borough[4]="Manhattan";
}
string borough[5];
int accident;
int temp;
};
All the class variables are public. Good class design would suggest that only the class functions are public with the class members being private (or possibly protected for classes used as a base class for other classes).
For each instance of the class, the borough array is going to contain the same data - but the accident variable is going to hold data relating to just one of the entries in borough. Which one is unknown!
You are using an array of CombineSort which itself contains the array.
Why have you defined getNumAccidents as?
Code:
int getNumAccidents(combineSort[], combineSort[]);
Why are you repeating the code in getNumAccidents for every borough? Why not a loop? What happens if the number of boroughs changes?
Possibly the simplest structure to use for this would be
Code:
struct BorData {
string name;
int accidents;
};
Then have an array of BorData (or even better use a vector).
As this is an assignment, I won't provide the code (see http://forums.codeguru.com/showthrea...ork-assignment) yet but if you post further revisions of your code we'll provide additional help and guidance.
Re: Sorting parallel arrays in C++
Thank you all for your advise. Let me work on it and make the recommended changes. If I have further issues I will let you know
Thanks
Re: Sorting parallel arrays in C++
Ok... I made changes to the code but now when I compile it, the borough array won't increment to the next value. so when it print to screen it says
"Enter number of accidents for New York City".....5 times... and after I enter five various number values in does give me the lowest but of course it say for the borough of New York City
Here is the new version of the code
Code:
#include<iostream>
#include<iomanip>
#include<string>
#include<cstring>
using namespace std;
struct BorData {
string borough[5]={"New York City","Bronx","Queens","Brooklyn","Manhattan"};
int accidents[5];
int temp;
};
int getNumAccidents(BorData[]);
int findLowest(BorData[]);
const int SIZE = 5;
/*********main*******/
int main()
{
BorData combine[SIZE];
int accidents[SIZE];
getNumAccidents(combine);
findLowest(combine);
return 0;
}
int getNumAccidents(BorData combine[])
{
for(int i=0;i<5;i++)
{
cout<<"\nEnter Number of Accidents for "<<*combine[i].borough<<endl;
cin>>*combine[i].accidents;
if(combine[i].accidents<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
}
}
int findLowest(BorData combine[])
{
int temp;
for(int i=0;i<5;i++){
if(*(combine[i].accidents)<*(combine[0].accidents)){
combine[i].temp=*(combine[i].accidents);
*(combine[i].accidents)=*(combine[0].accidents);
*(combine[0].accidents)=combine[i].temp;
}
}
cout<<"The lowest number of accident is: "<<*(combine[0].accidents)<<endl;
cout<<"In the Borough of: "<<*(combine[0].borough)<<endl;
return 0;
}
This is where I'm having problems with the for loop
Code:
int getNumAccidents(BorData combine[])
{
for(int i=0;i<5;i++)
{
cout<<"\nEnter Number of Accidents for "<<*combine[i].borough<<endl;
cin>>*combine[i].accidents;
if(combine[i].accidents<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
}
}
any suggestions as to what I'm doing wrong here...
thanks
Re: Sorting parallel arrays in C++
Quote:
any suggestions as to what I'm doing wrong here...
Yes - your data structures. If you include the arrays within the structure, then you don't need an array of BorData. You have either
1)
Code:
struct BorData {
string borough[5]={"New York City","Bronx","Queens","Brooklyn","Manhattan"};
int accidents[5];
};
...
BorData combine;
or 2)
Code:
struct BorData {
string borough;
int accident;
};
...
BorData combine[5] = {{"New York City", 0}, {"Bronx", 0}, {"Queens", 0}, {"Brooklyn", 0}, {"Manhattan", 0}};
Which way you choose then determines how you use the data.
for 1)
Code:
for (int i = 0; i < 5; i++)
{
cout "..... " << combine.borough[i];
cin >> combine.accidents[i];
}
for 2)
Code:
for (int i = 0; i < 5; i++)
{
cout "..... " << combine[i].borough;
cin >> combine[i].accidents;
}
Re: Sorting parallel arrays in C++
Ok almost there.. I'm still having the same sorting problems... the program compiles and runs fine except when its sorts. I do get the lowest number but I'm not getting the borough that correspond to it.
here's the new full code
Code:
#include<iostream>
#include<iomanip>
#include<string>
#include<cstring>
using namespace std;
struct BorData {
string borough;
int accidents;
};
int getNumAccidents(BorData[]);
int findLowest(BorData[]);
const int SIZE = 5;
/*********main*******/
int main()
{
BorData combine[5] = {{"New York City", 0}, {"Bronx", 0}, {"Queens", 0}, {"Brooklyn", 0}, {"Manhattan", 0}};
int accidents[SIZE];
getNumAccidents(combine);
findLowest(combine);
return 0;
}
int getNumAccidents(BorData combine[])
{
for(int i=0;i<5;i++)
{
cout<<"\nEnter Number of Accidents for "<<combine[i].borough<<endl;
cin>>combine[i].accidents;
if(combine[i].accidents<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
}
}
int findLowest(BorData combine[])
{
int temp[5];
for(int i=0;i<5;i++){
if(combine[i].accidents<combine[0].accidents){
temp[i]=combine[i].accidents;
combine[i].accidents=combine[0].accidents;
combine[0].accidents=temp[i];
}
}
cout<<"The lowest number of accident is: "<<combine[0].accidents<<endl;
cout<<"In the Borough of: "<<combine[0].borough<<endl;
return 0;
}
here's the sort function
Code:
int findLowest(BorData combine[])
{
int temp[5];
for(int i=0;i<5;i++){
if(combine[i].accidents<combine[0].accidents){
temp[i]=combine[i].accidents;
combine[i].accidents=combine[0].accidents;
combine[0].accidents=temp[i];
}
}
cout<<"The lowest number of accident is: "<<combine[0].accidents<<endl;
cout<<"In the Borough of: "<<combine[0].borough<<endl;
return 0;
}
Re: Sorting parallel arrays in C++
Code:
int accidents[SIZE];
You don't need this now as accidents are part of BorData.
Quote:
I do get the lowest number but I'm not getting the borough that correspond to it.
Thats because when you move .accidents from combine[i] to combine[0] you are also not moving .borough - so you aren't keeping the borough name consistent with the accident numbers.
Re: Sorting parallel arrays in C++
Quote:
Originally Posted by
gwiz01
I am not able to get the arrays to sort and match up correctly..
You don't have to sort to find the min (or max) element of an array.
You note the first element as the current min candidate. Then you scan the array and for each element check whether it's smaller than the min candidate. If so it becomes the new min candidate. When the scan finishes the min candidate is the smallest element of all.
So finding min or max can always be done in just one scan of an array. This is not true for sorting (if you find a way just book a ticket to Stockholm to pick up your Nobel prize :)) and that's why I can tell right away the "sorting" in findLowest doesn't work. If it seems to it's just accidental luck.
Finding an extreme element is O(N) whereas sorting is O(N * logN).
Re: Sorting parallel arrays in C++
Ok guys, I made more changes with the advice given which is very much appreciated..
now, when I compile and run for finding the lowest in borough I'm getting weird symbols like hearts and signs.
what am I doing wrong here :(
here is the complete code:
Code:
#include<iostream>
#include<iomanip>
#include<string>
#include<cstring>
using namespace std;
struct BorData {
string borough;
int accidents;
int smallest;
};
int getNumAccidents(BorData[]);
int findLowest(BorData[]);
const int SIZE = 5;
/*********main*******/
int main()
{
BorData combine[5] = {{"New York City", 0}, {"Bronx", 0}, {"Queens", 0}, {"Brooklyn", 0}, {"Manhattan", 0}};
getNumAccidents(combine);
findLowest(combine);
return 0;
}
int getNumAccidents(BorData combine[])
{
for(int i=0;i<5;i++)
{
cout<<"\nEnter Number of Accidents for "<<combine[i].borough<<endl;
cin>>combine[i].accidents;
if(combine[i].accidents<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
}
}
int findLowest(BorData combine[])
{
for(int i=0;i<5;i++)
{
combine[i].smallest=combine[0].accidents;
if ( combine[i].accidents<combine[0].smallest)
combine[0].smallest=combine[i].accidents;
combine[0].borough=combine[i].smallest;
}
cout<<"\nThe lowest number of accident is: "<<combine[0].smallest<<endl;
cout<<"In the Borough of: "<<combine[0].borough<<endl;
return 0;
}
Here is where I made changes to findLowest():
Code:
int findLowest(BorData combine[])
{
for(int i=0;i<5;i++)
{
combine[i].smallest=combine[0].accidents;
if ( combine[i].accidents<combine[0].smallest)
combine[0].smallest=combine[i].accidents;
combine[0].borough=combine[i].smallest;
}
cout<<"\nThe lowest number of accident is: "<<combine[0].smallest<<endl;
cout<<"In the Borough of: "<<combine[0].borough<<endl;
return 0;
}
Re: Sorting parallel arrays in C++
Code:
if ( combine[i].accidents<combine[0].smallest)
combine[0].smallest=combine[i].accidents;
combine[0].borough=combine[i].smallest;
One of your problems is that only the first assignment is controlled by the if statement as you are not using a compound statement. The other is that borough is of type string whereas smallest is of type int - so you are tyring to assign an int to a string!
Re: Sorting parallel arrays in C++
Yes!!!! yes yes... ok I got it. whew...:cry::thumb:
I think I going to name my first child "2kaud".. wifey will just have to understand :D
all I have to do is a little formatting but here's the final version...
Code:
#include<iostream>
#include<iomanip>
#include<string>
#include<cstring>
using namespace std;
struct BorData {
string borough;
int accidents;
int smallest;
string smallBorough;
};
int getNumAccidents(BorData[]);
int findLowest(BorData[]);
const int SIZE = 5;
/*********main*******/
int main()
{
BorData combine[5] = {{"New York City", 0}, {"Bronx", 0}, {"Queens", 0}, {"Brooklyn", 0}, {"Manhattan", 0}};
getNumAccidents(combine);
findLowest(combine);
return 0;
}
int getNumAccidents(BorData combine[])
{
for(int i=0;i<5;i++)
{
cout<<"\nEnter Number of Accidents for "<<combine[i].borough<<endl;
cin>>combine[i].accidents;
if(combine[i].accidents<0)
{
cout<<"Number has to be greater than 0";
return 0;
}
}
}
int findLowest(BorData combine[])
{
for(int i=0;i<5;i++)
{
combine[i].smallest=combine[0].accidents;
combine[i].smallBorough=combine[0].borough;
if(combine[i].accidents<combine[0].smallest)
{
combine[0].smallest=combine[i].accidents;
combine[0].smallBorough=combine[i].borough;
}
}
cout<<"\nThe lowest number of accident is: "<<combine[0].smallest<<endl;
cout<<"In the Borough of: "<<combine[0].smallBorough<<endl;
return 0;
}
thank you guys for all your help...
I have a few more projects to do. but that's another time lol... and my teachers methods is not the best as you can see. thank God for codeguru!!!
till next time take care :wave:
Re: Sorting parallel arrays in C++
Right, now that you have a working program now is the time to improve it.
1) You define the const SIZE as 5 but don't use it. You hard code 5 in various places.
2) getNumAccidents is defined as returning an int - but only returns a value when an error is found. Wouldn't it be better to display a message when there is an error in the data and then ask for the data to be entered again until it's right (use a loop)? In this case getNumAccidents doesn't need to return a value at all.
3) Your test is < 0 but your error message says has to be greater than 0. The two aren't the same!
4) You don't need to store smallest and smallBorough in the struct. The only variable you need is to hold the index of the smallest value in combine which should be a local variable to findLowest.
5) Although findLowest is 'working' it's not the most efficient way of doing it and uses extra variables in the struct. There is a much simpler way of doing this with findLowest only needing 6 lines of code.
6) findLowest is defined to return an int but you just return 0. Why not have findLowest return the index in combine of the lowest value? Then the cout statements in findLowest can be moved to main and findLowest then does what is expected from the name of the function. Someone using that function wouldn't really expect it to find the lowest and also display the info.
Have fun! :)
Re: Sorting parallel arrays in C++
Quote:
Originally Posted by
GCDEF
I hope the point of the exercise was to demonstrate what a pain parallel arrays are and how buggy they can be. If he's suggesting you write code that way, you need a new instructor.
There are cases where it's desired to do it this way. Particularly if you need locality of data. Splitting an array of structures up into multiple arrays of smaller elements/structures can sometimes cause a huge performance boost if it means you can get more data into the L1/L2 CPU cache. So it isn't an entirely pointless exercise unlike some others we've seen :-p.
But yes, it is a pain, it is error prone, and it means you can't use sorting libraries/templates unless they have a means to override/overload/templatize the element swap (and don't optimize it away in cases).
std::sort may not Always work with a custom swap() depending on implementation (small ranges can be sorted with an insertion sort which uses range swaps via move_backward. I'm not sure if c++11 made any guarantee changes on this...
so unless you relaly really have to, it's better to sort a single array of structures rather than trying to sort many arrays and keep them in sync.
Re: Sorting parallel arrays in C++
Quote:
Originally Posted by
OReubens
...it means you can't use sorting libraries/templates unless they have a means to override/overload/templatize the element swap (and don't optimize it away in cases).
You could always call the algorithm with a pair of boost::zip_iterators. You'll need to write a custom (or generic reusable) comparator though, which is not so nice without having support for generic lambdas (should come with C++14).