#include <iostream>

using namespace std;

int main()
{
    int row = 4, col = 4, sorted[16], mtr [4][4] = {
        {5,12,9,3},
        {6,2,11,7},
        {4,8,15,10},
        {1,13,16,14}
    };

    for(int r = 0; r < row; r++){
        for(int c = 0; c < col ; c++){
            cout<<mtr[r][c]<<"  ";
        }
        cout<<endl;
    }

    //Sort matrix in row form
    int i = 0;
    for(int r = 0; r < row; r++){
        for(int c = 0; c < col ; c++){
            sorted[i] = mtr[r][c];
            i++;
        }
    }

    // Apply Insertion sort
    for(int x = 1; x < 16; x++)
        for(int k = x; k > 0 && sorted[k- 1] > sorted[k]; k--)
            swap(sorted[k- 1], sorted[k]);

    // Print Row ordered matrix
    for(int r = 0,i=0; r < row; r++){
        for(int c = 0; c < col ; c++){
            mtr[r][c] = sorted[i];
            i++;
        }
    }
    for(int r = 0; r < row; r++){
        for(int c = 0; c < col ; c++){
            cout<<mtr[r][c]<<"  ";
        }
        cout<<endl;
    }

    // Print Column ordered matrix
    for(int r = 0,i=0; r < row; r++){
        for(int c = 0; c < col ; c++){
            mtr[c][r] = sorted[i];
            i++;
        }
    }
    for(int r = 0; r < row; r++){
        for(int c = 0; c < col ; c++){
            cout<<mtr[r][c]<<"  ";
        }
        cout<<endl;
    }


    return 0;
}