Sorting 2-D array in C++ using inbuilt std::sort function

Question

I have a matrix of the form pMat[M][N] (where M and N are variable and, hence, input from the user). I want to sort the elements of the 2-D array using the inbuilt std::sort function.

For example, consider the following array:

5 9 6
8 1 3
7 2 4

It should be output as:

1 2 3
4 5 6
7 8 9

The following is the code that I wrote for the purpose:

#include <iostream>
#include <algorithm>

int main() {
    int M, N, **pMat;
    std::cin >> M >> N;
    pMat = new int* [M];
    for (int i=0; i<M; i++){
        pMat[i] = new int[N];
    }
    for (int i=0; i<M; i++){
        for (int j=0; j<N; j++){
            std::cin >> pMat[i][j];
        }
    }
    std::sort(&pMat[0][0], (&pMat[0][0])+(M*N));
    for (int i=0; i<M; i++){
        for (int j=0; j<N; j++){
            std::cout << pMat[i][j] << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

I wrote the above code based on the following understanding:

Arrays in C++ are stored in contiguous memory locations
std::sort(add1,add2) sorts all the elements present in the memory locations [add1,add2)

The above code doesn't give the correct output. For example, when provided with the following input:

it displays the following output:

How can I go about writing the code? And where is my understanding wrong?

(For information, I looked at the following answer: Sort a 2D array in C++ using built in functions(or any other method)? , but it does not answer my query)

This won't work since you're working with an array of pointers, not a contiguous array. Since the array is always rectangular, you could instead use a contiguous array: int* pMat = new int[N*M] and std::sort(pMat, pMat + N*M). Note that that changes accessing from pMat[x][y] to pMat[(x*M)+y] (or similar) — alter_igel
– alter_igel, Commented Sep 21, 2018 at 4:46
Your array isn't really 2D. You want to load it in a single vector and sort it like that (then print N elements per line or whatever, it doesn't matter) — n.caillou
– n.caillou, Commented Sep 21, 2018 at 4:46
If you created your 2d array like this, your sort function would have worked with a couple of tweaks. The trick is that the data is contiguous. Wait -- it probably would have worked correctly now that I look closely at how you called sort. — PaulMcKenzie
– PaulMcKenzie, Commented Sep 21, 2018 at 4:51
This is probably the worst possible method of representing a 2D array in c++, and the worst possible data structure to store data that needs to be sorted in any language. Is this some kind of assignment? — n. m. could be an AI
– n. m. could be an AI, Commented Sep 21, 2018 at 5:15

Galik · Accepted Answer · 2018-09-21 08:35:48Z

One way to do this is to create one big array of contiguous (sortable) memory and then access that array as an array of sub-arrays through a second array of pointers.

The second array simply contains a list of pointers, each one pointing to a different sub-array within the larger one.

Something like this:

int M, N;

std::cin >> M >> N;

// one big array of actual data
// (an array of contiguous sub-arrays)
std::vector<int> v(M * N);

// array of pointers to sub-arrays within the actual data
std::vector<int*> pMat;

// point the pointers at the actual data
// each pointer pointing to the relevant sub-array
for(int i = 0; i < M; i++)
    pMat.push_back(v.data() + (i * N));

// get the input, changing the actual data
// through the pointers
for(int i = 0; i < M; i++)
    for(int j = 0; j < N; j++)
        std::cin >> pMat[i][j];

// sort the actual data
std::sort(std::begin(v), std::end(v));

// look at the data through the sub-array pointers
for(int i = 0; i < M; i++)
{
    for(int j = 0; j < N; j++)
        std::cout << pMat[i][j] << " ";
    std::cout << '\n';
}

return 0;

Note: I used std::vector to manage my arrays but it will also work with built in arrays created with new[] and delete[] (not recommended).

EDIT: To add.

Alternatively (much better) you can create a class that will store the data in a big contiguous block and access the different sub-arrays using mathematical offsets like this:

template<typename T>
class two_dee_array
{
public:
    two_dee_array(std::size_t M, std::size_t N): v(M * N), stride(N) {}

    T& operator()(std::size_t M, std::size_t N)
        { return v[(M * stride) + N]; }

    T const& operator()(std::size_t M, std::size_t N) const
        { return v[(M * stride) + N]; }

    std::size_t col_size() const { return stride; }
    std::size_t row_size() const { return v.size() / stride; }

    auto begin() { return std::begin(v); }
    auto end() { return std::end(v); }

    auto begin() const { return std::begin(v); }
    auto end() const { return std::end(v); }

    auto cbegin() const { return std::cbegin(v); }
    auto cend() const { return std::cend(v); }

private:
    std::vector<int> v;
    std::size_t stride;
};

int main()
{
    int M, N;

    std::cin >> M >> N;

    two_dee_array<int> v(M, N);

    for(int i = 0; i < M; i++)
        for(int j = 0; j < N; j++)
            std::cin >> v(i, j);

    std::sort(std::begin(v), std::end(v));

    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
            std::cout << v(i, j) << " ";
        std::cout << '\n';
    }
}

And it's fairly simple to provide row_range row(std::size_t); col_range col(std::size_t) with boost's stride and slice adaptors

kelalaka · Accepted Answer · 2018-09-21 07:43:56Z

As @alter_igel said. You problem is having non continuous array. Here corrected.

#include <iostream>
#include <algorithm>

int main() {

    int M, N, *pMat;
    std::cin >> M >> N;

    pMat = new int[M*N];

    for (int i=0; i<M; i++){
        for (int j=0; j<N; j++){
            std::cin >> pMat[i*N+j];
        }
    }
        std::cout << std::endl;

    std::sort(pMat, pMat+(M*N));

    for (int i=0; i<M; i++){
        for (int j=0; j<N; j++){
            std::cout << pMat[i*N+j] << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

Collectives™ on Stack Overflow

Sorting 2-D array in C++ using inbuilt std::sort function

2 Answers 2

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Linked

Related