Упорядочить все элементы матрицы таким образом, чтобы при чтении матрицы по строкам ее элементы образовывали отсортированный по возрастанию массив

@denstr · Регистрация: 21.11.2011

Студворк — интернет-сервис помощи студентам

Разработать программу, которая вводит целочисленную матрицу из n строк и m столбцов (1<n<=100, 1<m<=50) и Упорядочить все элементы матрицы таким образом, чтобы при чтении матрицы по строкам ее элементы образовывали отсортированный по возрастанию массив

Добавлено через 4 часа 12 минут
где то ошибка вот

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int main()
 
int i, t, j, i_min;
for(i=0; i<n*m-1; i++)
{
    i_min=i;
    for(j=i+1; j<n*m; j++)
        if(a[j/m][j%m]<a[i_min/m][i_min%m])
            i_min=j;
    t=a[i_min/m][i_min%m]; a[i_min/m][i_min%m]=a[i/m][i%m]; a[i/m][i%m]=t;
}

MrGluck · 06.12.2012, 05:03

Ну если по-простому, то так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>
#include <iterator>
#include <random>
#include <cstddef>
#include <vector>
 
 
int main()
{
    std::size_t M, N;
    std::cin >> M >> N;
    std::vector <std::vector<int> > A (M, std::vector<int> (N));
    std::random_device rd;
    std::mt19937 gen (rd());
    std::uniform_int_distribution<int> uid (10, 99);
    auto print_v = [](const std::vector<int>& v)
    {
        std::copy(v.begin(), v.end(), std::ostream_iterator<int> (std::cout, " "));
        std::cout << std::endl;
    };
    std::cout << "Before:\n";
    for (auto &v : A)
    {
        std::generate(v.begin(), v.begin() + N, [&uid, &gen] { return uid(gen); } );
        print_v(v);
        std::sort(v.begin(), v.end());
    }
    std::cout << "\nAfter:\n";
    for (auto &v : A)
        print_v(v);
}

@vladimirovna_ · 18.02.2021, 20:22

можете написать по проще на c++?

@Kuzia domovenok · 18.02.2021, 20:50

MrGluck, не упорядывачивает иначе как внутри строк
ожидалось
0123
3456
6789

@vladimirovna_ · 19.02.2021, 21:04

код можете написать?

@Catstail · 20.02.2021, 20:59

vladimirovna_,

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <algorithm>
 
using namespace std;
 
void sort_matr(int **x,int n)
{
    int *tmp=new int[n*n];
    int i,j,k;
    
    k=0;
    for (i=0; i<n; i++)
       for (j=0; j<n; j++)  tmp[k++]=x[i][j]; 
       
    sort(tmp,tmp+n*n);   
 
    k=0;
    for (i=0; i<n; i++)
       for (j=0; j<n; j++) x[i][j]=tmp[k++];
 
    delete [] tmp;
}
 
int main()
{
    int i,j;
 
    int **x=new int*[3];
    for (i=0; i<3; i++) x[i]=new int[3];
    
    x[0][0]=2;
    x[0][1]=8;
    x[0][2]=9;
    
    x[1][0]=7;
    x[1][1]=1;
    x[1][2]=5;
    
    x[2][0]=4;
    x[2][1]=3;
    x[2][2]=6;
 
    cout << "Исходная матрица:" << endl ;
    
    for (i=0; i<3; i++)
    {
        for (j=0; j<3; j++) cout << x[i][j] << " ";
        cout << endl;
    }
    
    sort_matr(x,3);
    
    cout << endl << "После сортировки:" << endl;
    
    for (i=0; i<3; i++)
    {
        for (j=0; j<3; j++) cout << x[i][j] << " ";
        cout << endl;
    }
    
    for (i=0; i<3; i++) delete [] x[i];
    delete [] x;
 
    return 0;
}

Вывод:

Исходная матрица:
2 8 9
7 1 5
4 3 6

После сортировки:
1 2 3
4 5 6
7 8 9

@oleg-m1973 · 20.02.2021, 21:41

Сообщение от denstr

Разработать программу, которая вводит целочисленную матрицу из n строк и m столбцов (1<n<=100, 1<m<=50) и Упорядочить все элементы матрицы таким образом, чтобы при чтении матрицы по строкам ее элементы образовывали отсортированный по возрастанию массив

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int main()
{
    srand(time(0));
 
    size_t n = 0;
    size_t m = 0;
    std::cout << "n: ";
    std::cin >> n;
 
    std::cout << "m: ";
    std::cin >> m;
 
    int *matrix = new int[n * m];
    for (size_t i = 0; i < n; ++i)
    {
        for (size_t j = 0; j < m; ++j)
        {
            matrix[i * m + j] = rand() % 90 + 10;
            std::cout << matrix[i * m + j] << " ";
        }
        std::cout << std::endl;
    }
    
    std::sort(matrix, matrix + m * n);
 
    std::cout << std::endl << "Sorted:" << std::endl;
    for (size_t i = 0; i < n; ++i)
    {
        for (size_t j = 0; j < m; ++j)
            std::cout << matrix[i * m + j] << " ";
 
        std::cout << std::endl;
    }
        delete[] matrix;
}

@Kuzia domovenok · 20.02.2021, 23:55

oleg-m1973, MrGluck, Catstail, Да вы все блин читеры, вместо того чтоб придумывать алгоритм 2д сортировки, пытаетесь срезать углы через использование библиотечных алгоритмов и декомпозиции на известные вам блоки.
Я напишу, что надо было автору
Catstail, в вашем коде замените

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void sort_matr(int** x, int n)
{
    bool sorted=false;
    while (!sorted) {
        sorted = true;
        int ipre = 0, jpre = 0;
        for (int i = 0; i < n; ++i) 
            for (int j = (i == 0 ? 1 : 0); j < n; ++j) {
                if (x[i][j] < x[ipre][jpre]) {
                    swap(x[i][j], x[ipre][jpre]);
                    sorted = false;
                }
                jpre = j;
                ipre = i;
            }
    }
}

@Catstail · 21.02.2021, 08:29

Kuzia domovenok, не согласен... В данном случае сортировка - подчиненная часть задачи. Вполне допустимо использовать библиотечную. А при необходимости можно и свою написать. Например, пузырьком:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
 
using namespace std;
 
void sort_matr(int **x,int n)
{
    int *tmp=new int[n*n];
    int i,j,k,c,t;
    
    k=0;
    for (i=0; i<n; i++)
       for (j=0; j<n; j++)  tmp[k++]=x[i][j]; 
       
    //sort(tmp,tmp+n*n);
    
    k=1;
    while(1)
    {
        c=0;
        for (i=0; i<n*n-k; i++)
            if (tmp[i]>tmp[i+1])
            {
                t=tmp[i];
                tmp[i]=tmp[i+1];
                tmp[i+1]=t;
                c++;
            }
            
        if (c==0) break;
        k++;
    }
 
    k=0;
    for (i=0; i<n; i++)
       for (j=0; j<n; j++) x[i][j]=tmp[k++];
 
    delete [] tmp;
}
 
int main()
{
    int i,j;
 
    int **x=new int*[3];
    for (i=0; i<3; i++) x[i]=new int[3];
    
    x[0][0]=2;
    x[0][1]=8;
    x[0][2]=9;
    
    x[1][0]=7;
    x[1][1]=1;
    x[1][2]=5;
    
    x[2][0]=4;
    x[2][1]=3;
    x[2][2]=6;
 
    cout << "Исходная матрица:" << endl ;
    
    for (i=0; i<3; i++)
    {
        for (j=0; j<3; j++) cout << x[i][j] << " ";
        cout << endl;
    }
    
    sort_matr(x,3);
    
    cout << endl << "После сортировки:" << endl;
    
    for (i=0; i<3; i++)
    {
        for (j=0; j<3; j++) cout << x[i][j] << " ";
        cout << endl;
    }
    
    for (i=0; i<3; i++) delete [] x[i];
    delete [] x;
 
    return 0;
}

@Kuzia domovenok · 21.02.2021, 11:19

Catstail, это опять-таки не сортировка двумерного массива, а копипаст. Тратится лишняя память и программист не напрягает мозг дабы определить алгоритм сортировки. Отличие только в том, что в первом случае программист вызвал библиотечную ф-ю, а во втором скопипастил стандартную сортировку. Я же предлагал поработать над собой и вложить (да, тоже не самую сложную, но) хоть немножечко неочевидную идею.

@oleg-m1973 · 21.02.2021, 11:31

Сообщение от Kuzia domovenok

oleg-m1973, MrGluck, Catstail, Да вы все блин читеры, вместо того чтоб придумывать алгоритм 2д сортировки, пытаетесь срезать углы через использование библиотечных алгоритмов и декомпозиции на известные вам блоки.

В смысле, читеры? Вообще, программирование в том и состоит, чтоб применять искать эффективные решения задач, а не пытаться кровь-из-носу вкрячить алгоритмы исходя из слова в названии.
В частности здесь из постановки задачи явно следует, что матрица должна быть представлена в виде одномерного массива. Тогда и не понадобятся все эти хитровыдуманные 2д-сортировки. Задача решается просто и эффективно.
Ну стандартный std::sort я использовал потому что целью у меня было показать идею реализации задачи в целом, а не расписывать алгоритмы сортировок.

@Catstail · 21.02.2021, 11:49

Сообщение от Kuzia domovenok

не сортировка двумерного массива

- а что такое "сортировка двумерного массива"? И не надо про копипаст - этим я не грешен, пишу сам.

Интуиция подсказывает, что если даже и придумать какой-то алгоритм, который сортировал бы двумерный массив, то это получится сложнее, чем то, что предложено выше. Тогда в чем смысл? Разе что в снижении расхода памяти для случая матрицы размером 10⁹*10⁹

@Kuzia domovenok · 21.02.2021, 12:35

oleg-m1973, окей, пусть будут эффективными по скорости, по затратам памяти. Пока что я вижу эффективность лишь во времени разработки, которая может быть нужна разве что всяким бизнесменам.

@oleg-m1973 · 21.02.2021, 12:59

Сообщение от Kuzia domovenok

Пока что я вижу эффективность лишь во времени разработки, которая может быть нужна разве что всяким бизнесменам.

В смысле? Хочешь сказать, что есть более эффективное решение этой задачи, чем то, которое показал я?

@Catstail · 21.02.2021, 15:15

Kuzia domovenok, вот сортировка двумерного массива без доп. памяти

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
 
using namespace std;
 
int getEl(int **m,int i,int n) // взять элемент
{
    int ii,jj;
    ii=i/n;
    jj=i%n;
    return m[ii][jj];
}
 
void putEl(int **m,int i, int n, int v) // положить элемент
{
    int ii,jj;
    ii=i/n;
    jj=i%n;
    m[ii][jj]=v;
}
 
void sort_matr(int **x,int n)
{
    int i,j,k,c,t,x1,x2;
    
    k=1;
    while(1)
    {
        c=0;
        for (i=0; i<n*n-k; i++)
        {
            x1=getEl(x,i,n);
            x2=getEl(x,i+1,n);
            if (x1>x2)
            {
                putEl(x,i,n,x2);
                putEl(x,i+1,n,x1);
                c++;
            }
        }    
        if (c==0) break;
        k++;
    }
 
}
 
int main()
{
    int i,j;
 
    int **x=new int*[3];
    for (i=0; i<3; i++) x[i]=new int[3];
    
    x[0][0]=2;
    x[0][1]=8;
    x[0][2]=9;
    
    x[1][0]=7;
    x[1][1]=1;
    x[1][2]=5;
    
    x[2][0]=-4;
    x[2][1]=3;
    x[2][2]=6;
 
    cout << "Исходная матрица:" << endl ;
    
    for (i=0; i<3; i++)
    {
        for (j=0; j<3; j++) cout << x[i][j] << " ";
        cout << endl;
    }
    
    sort_matr(x,3);
    
    cout << endl << "После сортировки:" << endl;
    
    for (i=0; i<3; i++)
    {
        for (j=0; j<3; j++) cout << x[i][j] << " ";
        cout << endl;
    }
    
    for (i=0; i<3; i++) delete [] x[i];
    delete [] x;
 
    return 0;
}

Вывод:

Исходная матрица:
2 8 9
7 1 5
-4 3 6

После сортировки:
-4 1 2
3 5 6
7 8 9

@Kuzia domovenok · 22.02.2021, 23:32

Catstail, ну вот это ок, хотя считаю свой код понятнее, без всяких адаптеров под псевдо 1д алгоритм

@Catstail · 23.02.2021, 07:08

Kuzia domovenok, зато мой универсальнее! Подмените ~~два метода~~ две функции - и он будет сортировать любые агрегаты. А ваш - нет.

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .

@vladimirovna_ 0 / 0 / 0 Регистрация: 18.02.2021 Сообщений: 51
	18.02.2021, 20:22
	можете написать по проще на c++? 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	18.02.2021, 20:50
	MrGluck, не упорядывачивает иначе как внутри строк ожидалось 0123 3456 6789 0

@vladimirovna_ 0 / 0 / 0 Регистрация: 18.02.2021 Сообщений: 51
	19.02.2021, 21:04
	код можете написать? 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	21.02.2021, 11:19
	Catstail, это опять-таки не сортировка двумерного массива, а копипаст. Тратится лишняя память и программист не напрягает мозг дабы определить алгоритм сортировки. Отличие только в том, что в первом случае программист вызвал библиотечную ф-ю, а во втором скопипастил стандартную сортировку. Я же предлагал поработать над собой и вложить (да, тоже не самую сложную, но) хоть немножечко неочевидную идею. 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	21.02.2021, 12:35
	oleg-m1973, окей, пусть будут эффективными по скорости, по затратам памяти. Пока что я вижу эффективность лишь во времени разработки, которая может быть нужна разве что всяким бизнесменам. 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	22.02.2021, 23:32
	Catstail, ну вот это ок, хотя считаю свой код понятнее, без всяких адаптеров под псевдо 1д алгоритм 0

@Catstail Супер-модератор 38167 / 21102 / 4307 Регистрация: 12.02.2012 Сообщений: 34,690 Записей в блоге: 14
	23.02.2021, 07:08
	Kuzia domovenok, зато мой универсальнее! Подмените ~~два метода~~ две функции - и он будет сортировать любые агрегаты. А ваш - нет. 0