How to sort a two dimensional array which is a part of a structure?

[sciman777]

hello, so if you look at my terrifying ugly code, I have an array of strings OSeat[][].sName, which I want to sort alphabetically. I know about the sort algorithm but it doesn't want to work with this (it gives no errors on my side of the code, but it gives an error on line 1900 something in the header file,,, so I'm pretty sure it can't handle this kind of data or something)

How would I go about sorting them?

Thank you!

also any advice on how to cut down on the length of the code is also highly appreciated! Have a nice day!

#include <iostream>
#include <string>
#include <algorithm>

const double cdPrice[4] ={150,100,75,50};
char cBuy = 'y';
int iSelectedPrice;
std::string sInputName;
int iSelectDay;
int iSelectMonth;
int iSelectYear;
char cTemp;
bool bFoundSeat = false;
int iTotalPay = 0;
bool bFoundName = false;


enum Section
{
    ORCHESTRA,
    FRONT,
    MIDDLE,
    BACK,
};

struct Date
{
    int iDay;
    int iMonth;
    int iYear;
};


struct Seat
{
    char cRow = 'n';
    int iColumn;
    Section SeatLoc;
    bool bAssigned;
    std::string sName;
    Date Day;
};


void vInitializer(Seat vOSeat[][50])
{
    for (int iX = 0; iX<26;iX++)
    {
        for (int iY = 0; iY<50;iY++)
        {
            vOSeat[iX][iY].cRow = (char)iX+65;
            vOSeat[iX][iY].iColumn = iY+1;
            vOSeat[iX][iY].bAssigned = false;
            vOSeat[iX][iY].sName = " ";
            vOSeat[iX][iY].Day.iDay = 1;
            vOSeat[iX][iY].Day.iMonth = 1;
            vOSeat[iX][iY].Day.iYear = 1900;
            if (vOSeat[iX][iY].cRow <= 'E')
                vOSeat[iX][iY].SeatLoc = ORCHESTRA;
            else if (vOSeat[iX][iY].cRow <= 'J')
                vOSeat[iX][iY].SeatLoc = FRONT;
            else if (vOSeat[iX][iY].cRow <= 'T')
                vOSeat[iX][iY].SeatLoc = MIDDLE;
            else
                vOSeat[iX][iY].SeatLoc = BACK;

        }
    }
}

void vDisplay(Seat vOSeat[][50])
{
     for (int iX = 0; iX<26;iX++)
    {
        for (int iY = 0; iY<50;iY++)
        {
            std::cout<< vOSeat[iX][iY].cRow<<" "<<vOSeat[iX][iY].iColumn<<" Section ";
            switch (vOSeat[iX][iY].SeatLoc)
            {
                case 0: std::cout <<"ORCHESTRA, Price $"<<cdPrice[0];
                        break;
                case 1: std::cout <<"FRONT, Price $"<<cdPrice[1];
                break;
                case 2: std::cout <<"MIDDLE, Price $"<<cdPrice[2];
                break;
                case 3: std::cout <<"BACK, Price $" <<cdPrice[3];
                break;
            }
            std::cout<<", "<<vOSeat[iX][iY].Day.iMonth<<"/"<<vOSeat[iX][iY].Day.iDay<<"/"<<vOSeat[iX][iY].Day.iYear<<std::endl;

        }
    }

}




int main()
{
    Seat OSeat[26][50];
    vInitializer(OSeat);
    vDisplay(OSeat);

    while (cBuy == 'y')
    {
        std::cout<<"Enter seat price"<<std::endl;
        std::cin>>iSelectedPrice;
        iTotalPay += iSelectedPrice;
        std::cout <<"Enter customer name"<<std::endl;
        std::cin.ignore();
        std::getline(std::cin,sInputName);
        std::cout<<"Enter date MM/DD/YYYY"<<std::endl;
        std::cin>>iSelectMonth>>cTemp>>iSelectDay>>cTemp>>iSelectYear;
        for (int iX = 0; iX<26;iX++)
        {
            for (int iY = 0; iY<50;iY++)
            {
                if(iSelectedPrice == 150 && iX <5)
                {
                    if(OSeat[iX][iY].sName==" " && bFoundSeat == false)
                    {
                            OSeat[iX][iY].sName = sInputName;
                            OSeat[iX][iY].Day.iDay = iSelectDay;
                            OSeat[iX][iY].Day.iMonth = iSelectMonth;
                            OSeat[iX][iY].Day.iYear = iSelectYear;
                            bFoundSeat = true;
                    }
                }
                if(iSelectedPrice == 100 && iX>4 && iX<10)
                {
                    if(OSeat[iX][iY].sName==" " && bFoundSeat == false)
                    {
                            OSeat[iX][iY].sName = sInputName;
                            OSeat[iX][iY].Day.iDay = iSelectDay;
                            OSeat[iX][iY].Day.iMonth = iSelectMonth;
                            OSeat[iX][iY].Day.iYear = iSelectYear;
                            bFoundSeat = true;
                    }
                }
                if(iSelectedPrice == 75 && iX>9 && iX<20)
                {
                    if(OSeat[iX][iY].sName==" " && bFoundSeat == false)
                    {
                            OSeat[iX][iY].sName = sInputName;
                            OSeat[iX][iY].Day.iDay = iSelectDay;
                            OSeat[iX][iY].Day.iMonth = iSelectMonth;
                            OSeat[iX][iY].Day.iYear = iSelectYear;
                            bFoundSeat = true;
                    }
                }
                if(iSelectedPrice == 50 && iX>19)
                {
                    if(OSeat[iX][iY].sName==" " && bFoundSeat == false)
                    {
                            OSeat[iX][iY].sName = sInputName;
                            OSeat[iX][iY].Day.iDay = iSelectDay;
                            OSeat[iX][iY].Day.iMonth = iSelectMonth;
                            OSeat[iX][iY].Day.iYear = iSelectYear;
                            bFoundSeat = true;
                    }
                }
            }
        }
        bFoundSeat = false;
        std::cout<<"Buy again?"<<std::endl;
        std::cin>>cBuy;
    }

    std::cout<<"assigned seats"<<std::endl;

    for(int iX = 0; iX<26;iX++)
    {
        for(int iY = 0; iY<50;iY++)
        {
            if (OSeat[iX][iY].sName !=" ")
                {std::cout<< OSeat[iX][iY].cRow<<" "<<OSeat[iX][iY].iColumn<<" Section ";
                switch (OSeat[iX][iY].SeatLoc)
                {
                    case 0: std::cout <<"ORCHESTRA, Price $"<<cdPrice[0];
                    break;
                    case 1: std::cout <<"FRONT, Price $"<<cdPrice[1];
                    break;
                    case 2: std::cout <<"MIDDLE, Price $"<<cdPrice[2];
                    break;
                    case 3: std::cout <<"BACK, Price $" <<cdPrice[3];
                    break;
                }
                std::cout<<", "<<OSeat[iX][iY].sName<<", purchase date "<<OSeat[iX][iY].Day.iMonth<<"/"<<OSeat[iX][iY].Day.iDay<<"/"<<OSeat[iX][iY].Day.iYear<<std::endl;
                }
        }
    }
    std::cout<<"Total price is $"<<iTotalPay<<std::endl;


    std::cout<<"Enter name to search for"<<std::endl;
    std::cin.ignore();
    std::getline(std::cin,sInputName);



    for (int iX = 0; iX<26;iX++)
    {
        for (int iY=0;iY<50;iY++)
        {
            if(OSeat[iX][iY].sName == sInputName)
            {
                 std::cout<< "Found at "<<OSeat[iX][iY].cRow<<" "<<OSeat[iX][iY].iColumn<<" Section ";
                 bFoundName = true;
            switch (OSeat[iX][iY].SeatLoc)
            {
                case 0: std::cout <<"ORCHESTRA, Price $"<<cdPrice[0];
                        break;
                case 1: std::cout <<"FRONT, Price $"<<cdPrice[1];
                break;
                case 2: std::cout <<"MIDDLE, Price $"<<cdPrice[2];
                break;
                case 3: std::cout <<"BACK, Price $" <<cdPrice[3];
                break;
            }
            std::cout<<", "<<OSeat[iX][iY].sName<<", Purchase date "<<OSeat[iX][iY].Day.iMonth<<"/"<<OSeat[iX][iY].Day.iDay<<"/"<<OSeat[iX][iY].Day.iYear<<std::endl;

            }
        }
    }

    if (!bFoundName)
        std::cout<<"Name not found!"<<std::endl;



getchar();
return 0;
}

[Handy Andy]

Hello sciman777,

I know about the sort algorithm but it doesn't want to work with this

. Of course not. There is nothing in the STL libraries that I know of for sorting a 2D array, but what is there works great on a 1D array. What you want to do is sort a 2D array of structs. This makes your life even more complicated.

Since you are storing a whole struct in the array a 1D array should be all you need or even a vector.

The error in some header file just means that what it can not handle is the extra dimension of your array.

Hope that helps,

Andy

[tpb]

Sorting doesn't necessarily make sense here. It's a 2D array. In what sense do you want it "sorted"? Starting with the lowest name at row 0 col 0 and moving along the cols and then to the next row etc?

Depending on what you are trying to achieve it may be best to scan the 2D array and make a 1D array of the info you want and sort that.

However, if you think sorting the 2D array makes sense, then you need to overload operator< to compare two Seats by name

bool operator<(const Seat& a, const Seat& b) {
    return a.sName < b.sName;
}

And you need to pass it like it's a 1D array

    std::sort(reinterpret_cast<Seat*>(&g[0][0]),
              reinterpret_cast<Seat*>(&g[25][49] + 1));

[Handy Andy]

Hello sciman777,

When I laid down last night I remembered a way to sort a 2D array. As tpb has already mentioned. Put the 2D array into a 1D array, sort the 1D array and then put it back into the 2D array.

So unless you write your own function, in which case tpb's suggestions would be useful, I believe the above approach is the simplest to work with.

Three tips that might be of use to you.

1. Line 5 you define the varable as a "const", but write the variable like any other variable. As a "const", or the newer version "constexpr", put the variable name in all caps. This will let you know that it is defined as a constant that can not be changed.

2. Lines 6 - 15. These are nice as global variables that the whole file has access to. As global variables these should be avoided and put in main or the functions that use them. Then pass what you need to the functions. As global variables any function in the program can change the values making it hard to track down what is causing a problem.

3. You should always initialize your variables where ever they are defined. And do not count on a global variable being initialized.

I will dig into the program more in a bit.

Hope that helps,

Andy

[Thomas1965]

It seems possible to pass a 2D array to the std::sort function.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>

const int N = 3;

int main()
{
  int numbers[N][N] = 
  {
    { 3, 2, 1},
    { 3, 2, 1 },
    { 3, 2, 1 },
  };

  std::sort(&numbers[0][0], &numbers[N-1][N]);

  for (int row = 0; row < N; row++)
  {
    for (int col = 0; col < N; col++)
    {
      std::cout << numbers[row][col] << '\t';
    }
    std::cout << '\n';
  }
}

Output:

1       1       1
2       2       2
3       3       3

CAUTION: I am not sure if it is guaranteed that a 2D array uses continuous memory.

[icy1]

How would I go about sorting them [by Seat::sName]?

tpb's answer

any advice on how to cut down on the length of the code

Not sure how much actual savings can be made, but you should definitely reorganize:
1. limit scope as much as possible -- you have a bunch of globals that are really only used in main
2. "26" and "50" are repeating everywhere so they should probably be global const ints ROWS and COLS or so.
3. Perfectly good bAssigned variable to check for Seat's vacancy, yet this is never assigned to true and you instead insist on initializing sName to a single blank space " " and then later comparing sName against this blank space.
Logic side-note: there are also dates, so in theory it should be possible to assign the exact same seat to multiple people, as long as dates don't overlap. Can come back to that later, or not at all, since that'd increase complexity of the program.
4. User doesn't know price of seats or how to enter Date parts (space-separated). Need to make prompts more descriptive.
5. Error-checking and illogical input. Without running it, looks like I could enter price of 1, and then it'd loop through everything, nothing would happen, and then I'd get "Buy again?"
6. Early exits and extra looping. Think carefully about places where you can break out of loops early because there's no point examining the rest.
6a. You can likely get rid of loop at line 172, which appears to show successfully assigned seats. At the moment of successful assignment, you could have another structure to remember successful coordinates or pointers to Seats. This structure would likely be much smaller than the whole auditorium, so looping through it would be more efficient instead of looping through all of ROWS, COLS, checking for blank space, etc.
6b. Separate searching away from buying, e.g. a Main Menu to buy seats or search. Not sure why user would want to search for a name immediately after buying seats every time.

Good luck :D

[sciman777]

Thank you everyone for your input! Unfortunately I still am unable to find a way of sorting them.

I tried

    std::sort(&OSeat[0][0].sName, &OSeat[25][49].sName);
    std::cout<<OSeat[0][0].sName;

and it did compile but when I run the program it crashes when it gets to that part. So I am still looking for a way to sort the array!

@tpb The thing is, I don't just want it to std::cout the members of the array in alphabetical order, the assignment is to *sort* the array, which I have no idea how to do since the fact that the array is of a structure and the string itself is in it, so it's messing things up.

@Handy Andy

Thanks for the suggestions! I really appreciate it!

1. I will be using the format you suggested from now on, simply because its what other programmers use. My own format was "cdPrice", c as in const, d as in double.

2. will do!

3. Will do!



Is tpb's answer the only way? I'm pretty sure the class hasn't done those yet.

In any case, thank you again very much!

[E0p9LyTq]

Unfortunately I still am unable to find a way of sorting them.

Do you want to sort the entire array's elements as if it was one big block regardless of row/column location, or sort by rows or columns?

The answers to those questions makes a difference in what you code.

[sciman777]

@FurryGuy

I want it to sort them in alphabetically, where OSeat[0][0].sName will be the first alphabetically, then OSeat[0][1].sName and so on.

I think the issue is that almost all of the sName's are " ", so the code is having trouble sorting them, because it compiles fine.

[sciman777]

I mean I think thats what I'm supposed to do, the assignment is worded very poorly.

I'm starting to think I'm just supposed to cout them in alphabetical order, that makes it much easier right? How would I do that?

[E0p9LyTq]

I want it to sort them in alphabetically

Then why have a 2D array? You can simulate a 2D array in a single dimension. Sorting a 1D array is EASY.

If you are storing the seating in a 2D so each array "row" is a different section based on your enum, still easy.

Using a 2D vector, a vector of vectors, is also relatively easy. Set your sort to work with the contained, inner vector.

Good data design can be a complicated problem, if you don't plan out what to do before you start coding.

[sciman777]

Yeah I get what youre saying, but my assignment wants a 2d array, but for the sorting part I think it might just want me to cout the names of the buys alphabetically. I can just make a new array of strings and store the names there.

Can you help me with that?

[icy1]

Self-contained example showing my advice from last comment (part 6a) to store pointers of bought seats in a vector. Then can sort with either bool operator overloading or a functor like below. I used very similar data structures but made the names readable, gave some constructors, etc.:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using std::vector;
using std::cout;
using std::endl;
using std::ostream;
using std::string;

enum Section
{
    ORCHESTRA,
    FRONT,
    MIDDLE,
    BACK,
};

struct Date
{
    Date() : 
        month(1),
        day(1),
        year(1900)
    {
    }
    
    Date(int month, int day, int year) :
        month(month),
        day(day),
        year(year)
    {
    }
    
    int month;
    int day;
    int year;
};

struct Seat
{
    Seat() :
        assigned(false)
    {
    }
    
    Seat(char row, int column, Section section, string name, Date date) :
        row(row),
        column(column),
        section(section),
        name(name),
        date(date),
        assigned(true)
    {
    }
    char row;
    int column;
    Section section;
    string name;
    Date date;
    bool assigned;
};

ostream& operator<<(ostream& os, const Seat& s) 
{
    string sectionstr;
    if (s.section == FRONT)
    {
        sectionstr = "FRONT"; 
    }
    else if (s.section == MIDDLE)
    {
        sectionstr = "MIDDLE";
    }
    else if (s.section == BACK)
    {
        sectionstr = "BACK";
    }
    else
    {
        sectionstr = "ORCHESTRA";
    }
    
    os << s.row << s.column << " " << sectionstr << " \""<<
          s.name << "\" " << s.date.month << "/" << s.date.day << "/" <<
          s.date.year << (s.assigned ? " ASSIGNED" : " NOT ASSIGNED") << endl;
    return os;
}

struct SeatSorter 
{
    bool operator()(const Seat& a, const Seat& b) 
    {
        return a.name < b.name;
    }
};

struct SeatPtrSorter 
{
    bool operator()(const Seat* a, const Seat* b) 
    {
        return a->name < b->name;
    }
};

int main() 
{
    // Or 2D array; doesn't matter
    vector<Seat> all_seats = 
    {
        { 'B', 47, ORCHESTRA, "John Doe", {4, 28, 2018} },
        { 'C', 22, FRONT, "Waylon Dalton", {5, 11, 2018} },
        { 'D', 16, MIDDLE, "Marcus Cruz", {9, 30, 2018} },
        { 'E', 4, MIDDLE, "Eddie Randolph", {11, 31, 2018} },
        { 'F', 55, MIDDLE, "Hadassah Hartman", {6, 30, 2018} },
        { 'G', 20, ORCHESTRA, "Justine Henderson", {6, 4, 2018} },
        { 'H', 33, FRONT, "Thalia Cobb", {5, 11, 2018} },
        { 'I', 1, BACK, "Angela Walker", {8, 2, 2018} },
        { 'J', 18, ORCHESTRA, "Joanna Shaffer", {7, 7, 2018} },
        { 'K', 4, BACK, "Abdullah Lang", {8, 8, 2018} },
        { 'L', 56, FRONT, "Mathias Little", {10, 31, 2018} },
        { 'M', 12, MIDDLE, "Lia Shelton", {12, 6, 2018} },
        { 'N', 3, ORCHESTRA, "Jonathon Sheppard", {6, 16, 2018} },
    };
    
    // Show all seats
    for (auto& seat : all_seats)
        cout << seat;
    
    cout << endl;
    
    // Some iteration (doesn't matter) to store particular seats
    vector<Seat*> some_subset;
    for (int i=0; i<all_seats.size(); ++i)
    {
        if (i&1)
            some_subset.push_back(&all_seats[i]);
    }
    
    // Some subset
    cout << "Subset with \"odd\" seats\n";
    for (auto seat_ptr : some_subset)
        cout << *seat_ptr;
        
    // Sorted subset
    std::sort(some_subset.begin(), some_subset.end(), SeatPtrSorter());
    cout << "\nSorted subset\n";
    for (auto seat_ptr : some_subset)
        cout << *seat_ptr;
}

Can run it at https://repl.it/repls/SharpIndolentFormula

Output:

B47 ORCHESTRA "John Doe" 4/28/2018 ASSIGNED
C22 FRONT "Waylon Dalton" 5/11/2018 ASSIGNED
D16 MIDDLE "Marcus Cruz" 9/30/2018 ASSIGNED
E4 MIDDLE "Eddie Randolph" 11/31/2018 ASSIGNED
F55 MIDDLE "Hadassah Hartman" 6/30/2018 ASSIGNED
G20 ORCHESTRA "Justine Henderson" 6/4/2018 ASSIGNED
H33 FRONT "Thalia Cobb" 5/11/2018 ASSIGNED
I1 BACK "Angela Walker" 8/2/2018 ASSIGNED
J18 ORCHESTRA "Joanna Shaffer" 7/7/2018 ASSIGNED
K4 BACK "Abdullah Lang" 8/8/2018 ASSIGNED
L56 FRONT "Mathias Little" 10/31/2018 ASSIGNED
M12 MIDDLE "Lia Shelton" 12/6/2018 ASSIGNED
N3 ORCHESTRA "Jonathon Sheppard" 6/16/2018 ASSIGNED

Subset with "odd" seats
C22 FRONT "Waylon Dalton" 5/11/2018 ASSIGNED
E4 MIDDLE "Eddie Randolph" 11/31/2018 ASSIGNED
G20 ORCHESTRA "Justine Henderson" 6/4/2018 ASSIGNED
I1 BACK "Angela Walker" 8/2/2018 ASSIGNED
K4 BACK "Abdullah Lang" 8/8/2018 ASSIGNED
M12 MIDDLE "Lia Shelton" 12/6/2018 ASSIGNED

Sorted subset
K4 BACK "Abdullah Lang" 8/8/2018 ASSIGNED
I1 BACK "Angela Walker" 8/2/2018 ASSIGNED
E4 MIDDLE "Eddie Randolph" 11/31/2018 ASSIGNED
G20 ORCHESTRA "Justine Henderson" 6/4/2018 ASSIGNED
M12 MIDDLE "Lia Shelton" 12/6/2018 ASSIGNED
C22 FRONT "Waylon Dalton" 5/11/2018 ASSIGNED