Sorting parallel arrays in C++
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Thread: Sorting parallel arrays in C++

Hybrid View

  1. #1
    Join Date
    Apr 2014
    Posts
    14

    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;

    }

  2. #2
    Join Date
    Apr 2014
    Posts
    14

    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;

    }

  3. #3
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    17,269

    Re: Sorting parallel arrays in C++

    Quote Originally Posted by gwiz01 View Post
    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!
    Victor Nijegorodov

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

    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.

  5. #5
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,757

    Re: Sorting parallel arrays in C++

    Quote Originally Posted by GCDEF View Post
    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.

  6. #6
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,010

    Re: Sorting parallel arrays in C++

    Quote Originally Posted by OReubens View Post
    ...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).
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  7. #7
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,262

    Re: Sorting parallel arrays in C++

    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

    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.
    Last edited by 2kaud; April 5th, 2014 at 08:25 AM.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  8. #8
    Join Date
    Apr 2014
    Posts
    14

    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

  9. #9
    Join Date
    Apr 2014
    Posts
    14

    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

  10. #10
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,262

    Re: Sorting parallel arrays in C++

    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;
    }
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  11. #11
    Join Date
    Apr 2014
    Posts
    14

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

  12. #12
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,262

    Re: Sorting parallel arrays in C++

    Code:
    int accidents[SIZE];
    You don't need this now as accidents are part of BorData.

    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.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  13. #13
    Join Date
    Jul 2013
    Posts
    201

    Re: Sorting parallel arrays in C++

    Quote Originally Posted by gwiz01 View Post
    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).
    Last edited by razzle; April 6th, 2014 at 04:56 AM.

  14. #14
    Join Date
    Apr 2014
    Posts
    14

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

  15. #15
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,262

    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!
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Page 1 of 2 12 LastLast

Tags for this Thread

Posting Permissions

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


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center