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

@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, зато мой универсальнее! Подмените ~~два метода~~ две функции - и он будет сортировать любые агрегаты. А ваш - нет.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

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

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

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

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

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