matrixSort.cpp

#include <iostream>
#include <vector>
#include <algorithm>
/*
Сортировка массива
Напишите алгоритм сортировки двумерного массива n на n такой, что A[i][j] ≤ A[k][m], если i+j < k+m. Постарайтесь использовать O(1) памяти.
Реализация алгоритма должна быть инкапсулирована.

Примеры работы программы
Ввод
3
1 3 2
7 8 9
6 8 9

Вывод
1 2 6
3 7 8
8 9 9

*/


class Matrix {
    std::vector<int> matrix;
    int matSize; // размерность матрицы
    int halfElements; // количество элементов в половине матрицы + главная диагональ

    void sortInternalMatrix() {
/*
Используется стандартная функция сортировки, т.к. она будет работать быстрее, чем самодельная реализация быстрой сортировки
из-за постоянного вызова подфункций (или неэффективной работы со стеком в случае итеративной быстрой сортировки).
Поэтому тут использование библиотечной функции даёт прирост в скорости из-за оптимизаций компилятора.

Известно, что в реализации данной функции лежит быстрая сортировка Хоара, которая не использует дополнительной памяти,
т.е. это O(1) дополнительной памяти. А вычислительная сложность алгоритма быстрой сортировки O(n*log(n)).
Соответственно, алгоритм очень эффективен как по памяти, так и по вычислениям.
*/
        std::sort(matrix.begin(), matrix.end());
    }
public:
    void readAndSortMatrix() {
        std::cin >> matSize;
        halfElements = matSize * (matSize + 1) / 2;
        matrix.resize(matSize * matSize);
        for (size_t i = 0, n = matrix.size(); i < n; i++) {
            std::cin >> matrix[i];
        }

        // Сортируем массив по возрастанию
        sortInternalMatrix();
    }
    void printSortedMatrix() {
        // Выводим результирующую матрицу хитрым образом, чтобы она возрастала по диагоналям в виде
        // 0 1 3
        // 2 4 6
        // 5 7 8
        /*
        Можно было бы построить и саму матрицу, но тогда мы бы использовали дополнительную память O(matSize*matSize),
        в момент построения матрицы. Т.к. по заданию рекомендовалось уложиться в O(1), то здесь используется алгоритм, который
        находит индекс нужного элемента в отсортированном масиве matrix без необходимости копирования.
        Таким образом, выполняется требование отсутствия использования дополнительной памяти.
        */

        int elementsBefore;
        for (int i = 0; i < matSize; i++) {
            for (int j = 0; j < matSize; j++) {
                // k - номер текущей диагонали
                // По нему определяем сколько элементов встретилось суммарно на диагоналях 0,1,..,k-1
                int k = i + j;
                if (k < matSize) {
                    elementsBefore = k * (k + 1) / 2;
                    std::cout << matrix[elementsBefore + i] << ' ';
                }
                else {
                    elementsBefore = halfElements + (3 * matSize - k - 1) * (k - matSize) / 2;
                    std::cout << matrix[elementsBefore + (matSize - j - 1)] << ' ';
                }
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    Matrix mat;
    mat.readAndSortMatrix();
    mat.printSortedMatrix();
    return 0;
}
/*
Общая вычислительная сложность алгоритма сортировки O(n*log(n)), она складывается из вычислительной сложности быстрой сортировки.
Сложность вывода отсортированного массива в виде убывания по антидиагоналям O(n), т.к. требуется пройтись всего один раз по всей матрице.
Общая эффективность по памяти O(N) и меньше нельзя, т.к. надо хранить саму матрицу хотя бы один раз в памяти. Она и хранится один раз.
Эффективность по памяти самого алгоритма сортировки O(1), т.е. он не использует дополнительную память
(разве что память в результате вызова, выделяемая подфункций на стеке, но совсем не использовать память не получится).
*/