Sort the Kth Column of the Matrix

Given a matrix mat[][] of size M x N integers where M is the number of rows and N is the number of columns and a number K. The task is to sort the Kth column of the matrix. Where K <= N.

Example:

Input: mat[3][3] = {{ 9, 3, 4},
      { 5, 2, 7},
      { 3, 1, 8}}
 K = 2
Output: mat[3][3] = {{ 9, 3, 4},
      { 2, 5, 7},
      { 3, 1, 8}}
Explanation: Here, K = 2 so sort the second column(3, 5, 1) to (1, 3, 5)

Input: mat[4][2] = {{4, 3},
     {6, 9},
     {1, 0},
     {2, 3}}
K = 1
   
Output: mat[4][2] = {{1, 3},
      {2, 9},
      {4, 0},
      {6, 3}}

Approach:

For Kth column in the given Matrix do the following:

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Iterate loop 0 to M-1, swap the value at these indexes and update the index as:
- if(mat[j][k-1]>mat[j+1][k-1])
  - swap(mat[j][k-1], mat[j+1][k-1])

Below is the implementation of the above approach:

// C++ implementation of the above approach

#include<bits/stdc++.h>

using namespace std;

const int M = 4;
const int N = 2;

// A utility function
// to swap the two element
void swap(int * a, int * b)

{

  int temp = * a;
  * a = * b;
  * b = temp;
}

// Function to sort
// the Kth column of the matrix
void sortKthColumn(int mat[M][N], int k)

{

  // Bubble sort
  for (int i = 0; i < M - 1; i++)

    // Last i elements are already in place
    for (int j = 0; j < M - i - 1; j++)
      if (mat[j][k - 1] > mat[j + 1][k - 1])
        swap( & mat[j][k - 1], & mat[j + 1][k - 1]);

  // Print the mat[][] after
  // sorting Kth column
  cout << "mat[" << M << "][" << N << "] = {" << endl;
  for (int i = 0; i < M; i++) {
    cout << "{ ";
    for (int j = 0; j < N; j++) {
      cout << mat[i][j] << ", ";
    }
    cout << "}," << endl;
  }
  cout << "}," << endl;
}

// Driver Code
int main() {

  int mat[][2] = { { 4, 3 }, { 6, 9 }, { 1, 0 }, { 2, 3 } };

  int K = 1;

  // Function call
  sortKthColumn(mat, K);

  return 0;
}

Output:

mat[4][2] = {
{ 1, 3, },
{ 2, 9, },
{ 4, 0, },
{ 6, 3, },
},

Time Complexity: O(m^2)
Space Complexity: O(1)

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.