Sorting an array (c++)

Question

I'm studying C++ and I had the task to create array[n][m], to fill it with integer numbers, then
"Characteristic of matrix rows is called the sum of its positive even elements. You need to sort the rows of the matrix in accordance with the growth of characteristics."

It's my code

#include "stdafx.h"
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
srand((unsigned)time(NULL));

int n, m;
cout << "n = ";
cin >> n;
cout << "m = ";
cin >> m;

int ** mas = new int * [n];
for (int i = 0; i < n; ++i)
{
    mas[i] = new int[m];
}

cout << "Array:\n";
for (int i = 0; i < n; ++i)
{
    for (int j = 0; j < m; ++j)
    {
        mas[i][j] = rand()%41-20;
        cout << mas[i][j] << "\t";
    }
    cout << "\n";
}

double * characteristic = new double[n];
for (int i = 0; i < n; ++i)
{
    characteristic[i] = 0;
}

for (int i = 0; i < n; ++i)
{
    for (int j = 0; j < m; ++j)
    {
        if((j%2 == 0) && (mas[i][j] >= 0)) 
        {
                characteristic[i] += mas[i][j];
        }
    }
}

cout << "Characteristics:\n";
for (int i = 0; i < n; ++i)
{
    cout << characteristic[i] << " ";
}
cout << "\n";

for (int i = 0; i < n - 1; ++i)
{
    int min = i;
    for (int j = i + 1; j < n; ++j)
    {
        if (characteristic[min] <= characteristic[j]) continue;
        min = j;
    }
    if (min != i)
    {
        double temp = characteristic[i];
        characteristic[i] = characteristic[min];
        characteristic[min] = temp;

        for (int k = 0; k < m; ++k)
        {
            int temp1 = mas[i][k];
            mas[i][k] = mas[min][k];
            mas[min][k] = temp1;
        }

    }
}

cout << "\nSorted characteristics:\n";
for (int i = 0; i < n; ++i)
{
    cout << characteristic[i] << " ";
}
cout << "\n";

cout << "Sorted array:\n";
for (int i = 0; i < n; ++i)
{
    for (int j = 0; j < m; ++j)
    {
        cout << mas[i][j] << "\t";
    }
    cout << "\n";
}

for (int i = 0; i < n; ++i)
{
    delete [] mas[i];
}
delete [] mas;

delete [] characteristic;

system("PAUSE");
return 0;
}

I created another one array for characteristics and sorted it and the first array at the same time, but it seems I used too difficult way to accomplish a given task. Maybe are there other ways?

Answer 1

Did you want to sort the matrix too, using the same ordering as the 'characteristic's?

Let's say you had C++ style code to calculate the characteristics:

std::vector<double> characteristic(n, 0.0);
std::transform(begin(mas), end(mas), begin(characteristic), sum_);

You could then sort them:

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

Or you could, indeed sort the matrix immediately:

std::sort(begin(mas), end(mas), [&sum_](int_vec const& a, int_vec const& b) 
         { return sum_(a)<sum_(b); });

Edit Fixed all versions to use the correct "characteristic sum" (kept the name though), thanks @Adam

Here's a full program that demonstrates this: See it Live on Coliru

#include <random>
#include <iostream>
#include <string>
#include <vector>

#include <cstdlib>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    typedef std::vector<int> int_vec;

    srand((unsigned)time(NULL));
    int n, m;
    cout << "n = ";
    cin  >> n;
    cout << "m = ";
    cin  >> m;

    std::vector<int_vec> mas(n, int_vec(m));

    for (auto& v : mas)
        std::for_each(begin(v), end(v), [](int& i) { i = rand()%41-20; });

    cout << "Array:\n";
    for (auto const& v : mas)
    {
        std::copy(begin(v), end(v), ostream_iterator<int>(cout, "\t"));
        cout << "\n";
    }

    auto sum_ = [m](int_vec const& v) { 
        double vchar = 0;
        for (auto j = 0; j < m; j+=2)
            if(v[j] >= 0) vchar += v[j];
        return vchar;
    };

    std::vector<double> characteristic(n, 0.0);
    std::transform(begin(mas), end(mas), begin(characteristic), sum_);

    cout << "Characteristics:\n";
    std::copy(begin(characteristic), end(characteristic), ostream_iterator<double>(cout, " "));
    cout << "\n";

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

    cout << "\nSorted characteristics:\n";
    std::copy(begin(characteristic), end(characteristic), ostream_iterator<double>(cout, " "));
    cout << "\n";

    std::sort(begin(mas), end(mas), [&sum_](int_vec const& a, int_vec const& b) { return sum_(a)<sum_(b); });

    cout << "Sorted Array:\n";
    for (auto const& v : mas)
    {
        std::copy(begin(v), end(v), ostream_iterator<int>(cout, "\t"));
        cout << "\n";
    }

}

Sample output:

n = m = Array:
11  15  19  18  
-20 -16 2   -11 
8   2   19  8   
Characteristics:
30 2 27 

Sorted characteristics:
2 27 30 
Sorted Array:
-20 -16 2   -11 
8   2   19  8   
11  15  19  18  

Answer 2

@sehe gives you great advice, but I suspect a lot of that stuff won't make sense until you know more C++.

Here's a simple improvement to eliminate a slow loop:

When doing your row swaps swap the row pointers instead of copying every value that they point to. Replace this:

    for (int k = 0; k < m; ++k)
    {
        int temp1 = mas[i][k];
        mas[i][k] = mas[min][k];
        mas[min][k] = temp1;
    }

With:

    int* temp1 = mas[i];
    mas[i] = mas[min];
    mas[min] = temp1;

If you can figure out how to use a built-in sort algorithm that would be another improvement on top of this, but even this small change will gain you a lot.

Answer 3

Since the sizes n,m are known in compile time, you can use the qsort function from the C library.

#include <stdlib.h>

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

Where is compar is a function you write, which should treat both its arguments as pointers to a row of the matrix. Then it can calculate the characteristic of both rows, and return -1, 0 or 1 depending on which row's characteristic is greater.