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?

try std::vector of std::vectors and then std::sort using a custom predicate, then it'll look like c++ — Dmitry Ledentsov
– Dmitry Ledentsov, Commented Oct 11, 2013 at 6:38
Why do you use double for characteristic, if the matrix only contains ints? — SingerOfTheFall
– SingerOfTheFall, Commented Oct 11, 2013 at 6:38
If you are free to choose your own matrix structure then instead of a 2D array use what Dmetry suggests, or an array of pointers to 1D arrays. That way you can swap entire rows by simply swapping pointers (or vector.swap()). That takes your row swaps from O(n^2) to O(n). — Adam
– Adam, Commented Oct 11, 2013 at 6:49
@n.m. Actually, I'm going to call you out on the std::array thing: n and m are dynamic. YOU tell me how to make a dynamically sized std::array. — Adam
– Adam, Commented Oct 11, 2013 at 7:47
@Adam again, agreed :) My answer would have been using std::array<> if it weren't for that — sehe
– sehe, Commented Oct 11, 2013 at 7:53

sehe · Accepted Answer · 2013-10-11 09:43:38Z

3

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

edited Oct 11, 2013 at 9:43

answered Oct 11, 2013 at 7:07

sehe

400k49 gold badges475 silver badges673 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

sehe Over a year ago

Using c++11's <random> header is left as an exercise to the reader for now. Do read How do I scale down numbers from rand()? and rand() Considered Harmful by Stephan Lavavej, though.

Heidel Over a year ago

thanks a lot for your explanation, but I have not studied vector yet.

Adam Over a year ago

@sehe am I missing something or does your mas sort recompute the characteristics for every comparison? Also it seems sum_ makes the characteristic the sum of all elements, not just the positive even ones.

sehe Over a year ago

@Adam you're right on both. I never even noticed the check for positive even ones. Oh and now I see: you meant positive ones at even indices :). Will fix

Adam Over a year ago

do you know the C++ish way to fix the former? All I can think of is to sort the characteristics vector while keeping track of the permutation, then permute mas using the same permutation. It's what I do in my own codes but it's messy and I couldn't find a standard permutation function.

|

Adam · Accepted Answer · 2013-10-11 09:12:45Z

1

@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.

answered Oct 11, 2013 at 9:12

Adam

17.4k8 gold badges55 silver badges103 bronze badges

1 Comment

Adam Over a year ago

@Heidel no problem. After your final exams come back to look at sehe's code. It will make you a better C++ programmer. It also highlights some differences between C and C++ and why they really are different languages that only resemble each other.

SzG · Accepted Answer · 2013-10-11 06:54:26Z

0

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.

answered Oct 11, 2013 at 6:54

SzG

12.7k4 gold badges31 silver badges43 bronze badges

6 Comments

cdoubleplusgood Over a year ago

Honestly? qsort is C and not type safe. I'd recommend std::sort.

sehe Over a year ago

@cdoubleplusgood See my answer (although this is likely homework, and my answer is going to be of little use unless the teacher is surprisingly open-minded about using post-1990 C++ in class :))

Adam Over a year ago

@SzG n and m are not known at compile time. Obviously you can still write a comparator function, but I think you'd have to resort to global variables. std::sort doesn't have that problem, you can use a comparator object instead.

SzG Over a year ago

@cdou Yes I know C is evil, not type-safe and totally incompatible with C++. That's why e.g the Linux kernel is using C++. Oh wait...

cdoubleplusgood Over a year ago

@SzG: The question is about C++, not C.

|

Collectives™ on Stack Overflow

Sorting an array (c++)

3 Answers 3

9 Comments

1 Comment

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

9 Comments

1 Comment

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related