Как отсортировать только правильную четверть матрицы 10 x 10?

Question

* Матрица

10x10, которая разделена на 4 части, правая четверть отсортирована по any_method в строках:

Я начинающий. Я совершенно не понимаю, как на самом деле работает алгоритм выбора нужной четверти для его дальнейшей сортировки. Вот что у меня на данный момент.

#include <iostream>
#include <ctime>
using namespace std;

int main()
{
srand(time(0));

const int size = 10;
int matrix[size][size];
int sum = 0;

system("mode con cols=100 lines=70");

cout << "Source matrix 10x10" << endl;
cout << endl;

for (int i = 0; i < size; i++)
{
    for (int j = 0; j < size; j++)
    {
        matrix[i][j] = rand() % 50;   
    }
}

for (int i = 0; i < size; i++)
{
    for (int j = 0; j < size; j++)
    {
        cout << matrix[i][j] << "\t";
    }
    cout << endl << endl;
}

cout << endl;
cout << "Transformed matrix 10x10" << endl;

int temp;
int k = 0;
int cond = 0;

for (int s = 0; s < size; s++)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = size - 1; j > i; j--)
        {    
            if (matrix[s][j] < matrix[s][j - 1])
            {
                temp = matrix[s][j];
                matrix[s][j] = matrix[s][j - 1];
                matrix[s][j - 1] = temp;
            }
        }
    }
}

for (int i = 0; i < size; i++)
{
    for (int j = 0; j < size; j++)
    {
        cout << matrix[i][j] << "\t";
    }
    cout << endl << endl;
}

cout << endl << sum << endl;

return 0;
system("pause");

}

Answer 1

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

Я использовал std::sort, чтобы продемонстрировать сортировку правой четверти из 10 x 10 матрица .

Моя логика c объясняется в комментариях к коду:

void sortRightQuarter(int m[10][10])
{
    /*
    Indexes of the elements in the Right Quarter
                                    (0, 9) // already sorted
                            (1, 8), (1, 9) // i = 1, k = 8
                    (2, 7), (2, 8), (2, 9) // i = 2, k = 7
            (3, 6), (3, 7), (3, 8), (3, 9) // i = 3, k = 6
    (4, 5), (4, 6), (4, 7), (4, 8), (4, 9) // i = 4, k = 5
    (5, 5), (5, 6), (5, 7), (5, 8), (5, 9) // i = 5, k = 5
            (6, 6), (6, 7), (6, 8), (6, 9) // i = 6, k = 6
                    (7, 7), (7, 8), (7, 9) // i = 7, k = 7
                            (8, 8), (8, 9) // i = 8, k = 8
                                    (9, 9) // already sorted
    */

    // Sort the rows [1, 8]
    int k = 8;
    for (int i = 1; i <= 8; ++i)
    {
        // pick your favorite sorting function
        // to sort elements in the range [m[i][k], last element of the row]
        sort(&m[i][k], &m[i][10]);

        // change the value of k
        if (i < 4)
            --k;
        else
            ++k;
    }
}

Я использовал ваш код для проверки своей функции. Работает хорошо.

Answer 2

Пусть M - матрица размером K x K, например, K должно быть либо:

1. A K, например k = 2 * n, где n не является отрицательное целое число.
2. A K, например k = 2 * n + 1, где n - неотрицательное целое число.

Теперь для решения алгоритмической c части получения только часть в самой правой четверти; Обозначим row и col в качестве номеров строк и столбцов.

Случай 1:

для row <= n необходимые ячейки имеют значение col >= k - row + 1

для row >= n + 1 необходимые ячейки имеют col >= row

Случай 2:

для row <= n + 1 необходимые ячейки имеют col >= k - row + 1

для row > n + 1 необходимые ячейки имеют col >= row

Как вы можете добраться до этого? Просто сядьте с бумагой, нарисуйте матрицу и посмотрите на нужные ячейки. Определите, в каких «ключевых точках» меняется правило, и вы получите ответ.

Answer 3

Можно разделить код на более мелкие функции, но для выполнения sh вашей задачи все, что вам нужно сделать, это применить функцию сортировки к соответствующей части каждой строки в матрице:

for (int i = 0,     // Index of the row and the column of the elements on the main diagonal
     j = size - 1;  // Column of the element on the anti-diagonal
     i < size;
     ++i, --j)
{        
    int *row = &matrix[i][0];                      // Start of the row
    std::sort(row + std::max(i, j), row + size);
    //              ^^^^^^^^^^^^^^ Pick the right one
}

Также обратите внимание на конец программы

return 0;
system("pause");   // <-- How this could be executed? Not that it should, BTW.