Basic sorting of 2D Arrays-CodePudding

I cannot for the life of me figure out how to sort a 2D array while maintaining consistency with the array's structure. For instance, I have an array say...

myArray[4][3] = {{"Tom", "yes", "yes"},
                 {"Bob", "yes", "no"},
                 {"Chris", "no", "no"},
                 {"Bill", "no", "yes"}};

That when sorted should translate to...

myArray[4][3] = {{"Bill", "no", "yes"},
                 {"Bob", "yes", "no"},
                 {"Chris", "no", "no"},
                 {"Tom", "yes", "yes"}};

If I am phrasing my question correctly, in essence, I am trying to move the entire row in ascending order based on the element located in column 0.

CodePudding user response：

As suggested, a struct makes this much simpler. It also keeps your relevant data together for you, as it appears that a row is all related to a single entry.

Here's some code that demonstrates the principle:

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

struct Client {
  std::string name;
  bool one = false;
  bool two = false;

  Client(std::string n, bool r, bool a) : name(n), one(r), two(a) {}
};

bool operator<(const Client& lhs, const Client rhs) {
  return lhs.name < rhs.name;
}

std::ostream& operator<<(std::ostream& sout, const Client& client) {
  return sout << std::boolalpha << client.name << ", " << client.one << ", "
              << client.two;
}

template <typename Container>
void print(const Container& c) {
  for (auto i : c) {
    std::cout << i << '\n';
  }
}

int main() {
  std::array<Client, 4> clients{{{"Tom", true, true},
                                 {"Bob", true, false},
                                 {"Chris", false, false},
                                 {"Bill", false, true}}};

  print(clients);
  std::sort(clients.begin(), clients.end());
  std::cout << "\n\n";
  print(clients);
}

Each row is now an object, which makes keeping track of a client, in this case, much easier than ensuring all the disparate data pieces travel together.

Because each row was compacted to an object, you now have a 1D array instead of a 2D array, and sorting those are trivial.

Here, I use operator<() instead of the new in C 20 operator<=>() because my compiler is giving me a hard time with the C 20 stuff generally (I need to check my version's compatibility and upgrade if possible).

Output:

Tom, true, true
Bob, true, false
Chris, false, false
Bill, false, true


Bill, false, true
Bob, true, false
Chris, false, false
Tom, true, true

Another note, and one that I didn't want to add code to keep the answer clean(er) would be to create types for the bools using enum classes. This way, instead of trying to remember what the second bool is supposed to represent, you'd have the type name with a clear value instead. Again, it adds a bit more boilerplate, so I kept it out of this answer, but it is a huge help to code readability.

CodePudding user response：

I still would like to know how the format is for sorting this way with a 2D array. I can’t visualize it through my readings.

Okay.

The tl;dr is, the C standard library is built to assume container elements are copyable with operator=, which raw C arrays are very much not, and to get past that with arrays as data elements like you've got here you need to tell C to use C semantics on them, with std::array<const char*,3> as its type.

#include <iostream>
#include <algorithm>
#include <array>
#include <cstring>

std::array<const char *,3> myarray[] = {
    {"Tom", "yes", "yes"},
    {"Bob", "yes", "no"},
    {"Chris", "no", "no"},
    {"Bill", "no", "yes"}
};
int main()
{
    using namespace std;
#define λlr(expr) [](auto &l, auto &r) { return expr; }
    sort(begin(myarray), end(myarray), λlr(strcmp(l[0],r[0])<0));
    for ( auto &row : myarray )
        cout <<'\t'<<row[0] <<'\t'<<row[1] <<'\t'<<row[2] <<'\n';
}

edit: if you're stuck with the raw C arrays exactly as shown for your data type, you're going to have to use the C library for your sorting, and if you're using a C compiler you're going to have to reassure its type safety checking about the function you're passing:

qsort(myarray, sizeof myarray / sizeof *myarray, sizeof *myarray, 
        (int(*)(const void*,const void*))strcmp);`

or get horribly cute with your iterators:

{ typedef array<const char*,3> *member;
  sort(member(begin(myarray)),member(end(myarray), λlr(strcmp(l[0],r[0])<0));
}

CodePudding user response：

You can actually sort your raw array directly if you need to. To do this, we use a indexing array that keeps track of std::sort's swaps. This can be used to create an inversion array and then invert the original raw array with std::swap. The latter will make sure that the internal consistency is invariant.

#include <algorithm>
#include <numeric>
#include <cstring>

template <std::size_t N, std::size_t M>
void sort(char const* (&a)[N][M]) {
  std::size_t idx[N] {}; // meaning: slot x wants entry idx[x]
  std::iota(std::begin(idx), std::end(idx), 0u); // 0, 1, 2, 3, ..., N-1

  std::sort(std::begin(idx),std::end(idx),[&](std::size_t const lhs, std::size_t const rhs) {
    return std::strcmp(a[lhs][0],a[rhs][0]) < 0;
  });

  // idx is now: 3, 1, 2, 0

  std::size_t inv[N] {}; // meaning: entry y wants to go to slot inv[y]
  for (std::size_t i = 0; i < N;   i) {
    inv[idx[i]] = i;
  }

  // inv is now: 3, 1, 2, 0

  for (std::size_t i = 0; i < N;   i) {
    while (inv[i] != i) { // keep permutating until a[i] has the correct entry
      std::swap(a[i], a[inv[i]]);
      std::swap(inv[i], inv[inv[i]]);
    }
  }
}

You can call this with your example array:

sort(myArray);

Although it doesn't immediately look like it, the last inversion loop (the one containing the while-loop) is actually linear in N (counting the number of swaps). Each swap moves some line to the final slot it has to end up in. So even if a single iteration of the outer for loop may swap a lot of entries around, each of those is final and eventually it will move the correct entry to slot i.