сортировать строки матрицы в порядке возрастания лексикографии

Question

Привет, мне нужна помощь с одним из домашних заданий.Мне нужно улучшить скорость кода, который у меня есть, пожалуйста, помогите мне?

Это мой код:

int main(int argc, char** argv) {
    int n,m;
    scanf("%d %d",&n,&m);
    int table[n][m];

    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++)
        {
            cin>>table[i][j];
        }
    }

    bool isSorted = false;

    while (!isSorted) {
        isSorted = true;

        for(int i=0;i<n - 1;i++)
        {
            std::string str = "";
            std::string str2 = "";
            for(int j=0;j<m;j++) {
                str += table[i][j] + '0';
                str2 += table[i+1][j] + '0';
            }

            // cout << str2 << " < " << str << " Bool " << (str2 > str) << endl;

            if (str2 < str) {
                for (int k = 0; k < n; k++)
                {
                    int t = table[i][k];
                    table[i][k] = table[i + 1][k];
                    table[i + 1][k] = t;
                }
                isSorted = false;
                break;
            }

        }
    }

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        cout<<table[i][j]<<" ";
        cout<<endl;
    }

    return 0;
}

Задача: Матрица с M строками и N лестницей.Сортировать строки матрицы в возрастающем лексикографическом порядке, т. Е. Если A = A (1), A (2), ..., A (n) и B = B (1), B (2) ...,B (n) - две строки матрицы, такие что A (1) = B (1), A (2) = B (2) и A (k + 1) B (k + 1) отсортированная матрица.

Формат ввода

Каждый из следующих ключей должен быть указан в таблице ниже.

Constraints

3<M<1024, 3<N<1024

Формат вывода

Вам необходимо вычислить матрицу.

Sample Input

4 4
6 1 1 2
7 2 9 4
7 3 1 5
7 2 9 3

Sample Output

6 1 1 2
7 2 9 3
7 2 9 4
7 3 1 5

Answer 1

Я бы хотел поддержать вас и показать одно из многих возможных решений.

В вашей программе все еще много элементов в стиле C, таких как обычные массивы или scanf. Я бы хотел перейти на современный C ++.

Настоятельно рекомендуется использовать STL и алгоритмы.

И в наше время люди всегда будут использовать контейнеры STL, такие как std :: vector из std :: vector, для реализации концепции матрицы.

Я буду встраивать все в класс.

Чтение и запись значений будут выполняться с помощью библиотеки iostream. А для определенных пользователем типов оператор извлечения и вставки (>> и <<) будет перезаписан. При этом возможно простое использование существующих возможностей io. </p>

Алгоритмы могут использоваться для работы с частями или целым контейнером. И поэлементные операции для контейнерных элементов будут выполняться с использованием итераторов. Как вы увидите, мы «копируем» значения из входных данных в матрицу и обратно в выходные данные.

Итак, в приведенном ниже листинге вы увидите основные задачи, выполняемые в 3 строчки кода.

Обратите внимание: сортировка выполняется очень быстро. И это работает, потому что оператор менее чем (<) также присутствует для std :: vectors </p>

Пожалуйста, смотрите:

РЕДАКТИРОВАТЬ: Код обновлен в соответствии с комментарием Л.Ф.

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>


// Constraints for number of rows and columns
constexpr int ConstraintMin = 3;
constexpr int ConstraintMax = 1024;
// Custom Class to hold a matrix
class Matrix
{
public:
    // Explicit constructor. Make a matrix with the requested numbers of rows and columns
    explicit Matrix(const size_t numberOrRows, const size_t numberOfColumns) { matrix.resize(numberOrRows); std::for_each(matrix.begin(), matrix.end(), [numberOfColumns](Columns & c) { c.resize(numberOfColumns); });     }
    // Main Function of Matrix: Sort.  
    void sort() { std::sort(matrix.begin(), matrix.end()); }

    // Overload extratcor.  Read all data for Matrix from an istream
    friend std::istream& operator >> (std::istream& is, Matrix& m) {
        std::for_each(m.matrix.begin(), m.matrix.end(), [&is](Columns& columns) {std::copy_n(std::istream_iterator<int>(is), columns.size(), columns.begin()); });
        return is;
    }
    // Overload inserter. Write Matrix to ostream
    friend std::ostream& operator << (std::ostream& os, const Matrix& m) {
        std::for_each(m.matrix.begin(), m.matrix.end(), [&os](const Columns & columns) {std::copy_n(columns.begin(), columns.size(), std::ostream_iterator<int>(os, " ")); std::cout << '\n'; });
        return os;
    }
protected:
    // The columns in one row of the matrix
    using Columns = std::vector<int>;
    // The container for the data. A vector of columns
    std::vector<Columns> matrix{};
};

int main()
{
    // This will hold the number of rows and columns of our matrix
    int rows{ 0 }, columns{ 0 };

    std::cout << "\nMatrix Sort\n\nEnter the number of rows and columns of the matrix:\n";

    // Read number of rows and columns from user
    std::cin >> rows >> columns;
    // Keep values in limit constraints
    rows = std::min(std::max(ConstraintMin, rows), ConstraintMax);
    columns = std::min(std::max(ConstraintMin, columns), ConstraintMax);

    // Define the matrix with the given numbers of rows and columns
    Matrix matrix(rows, columns);

    std::cout << "\nPlease enter " << rows << " rows and " << columns << " columns:\n";

    // Read the complete matrix
    std::cin >> matrix;
    // Sort it
    matrix.sort();
    // And show the result
    std::cout << "\n\nResult. Sorted matrix:\n" << matrix;

    return 0;
}

Надеюсь, я мог бы дать вам небольшое представление о мощи современного C ++. , .