The matrix sort problem

The matrix sort problem entails sorting based on a column in ascending or descending fashion while ensuring the order of the elements with respect to other rows, respectively.

Sample program


Matrix :
		  4  3  2  1  5
		  5  2  5  4  6
		  1  2  3  5  7
		  8  9  6  3  2
		  1  3  5  7  9

Matrix Sort (based on the last column)
		  8  9  6  3  2
		  4  3  2  1  5
		  5  2  5  4  6
		  1  2  3  5  7
		  1  3  5  7  9

We’ll use the famous bubble sort algorithm to achieve this. However, before we head into the algorithm, let’s build some auxiliary functions to make our algorithm easier to code.

Swapping two elements

When we apply the bubble sort algorithm on a 1-D array, we essentially swap elements to position them in the appropriate place. To swap two elements, we leverage the swap method defined in the algorithm library in C++. It is a standard library function that can swap the values of two variables. of C++.

The algorithm library in C++ is a part of the STL. The Standard Template Library or STL is a set of C++ template classes to provide common programming data structures and functions. It is designed to make it easier to write efficient and reusable code by providing a consistent and well-documented interface for common programming tasks.

The code snippet below demonstrates the usage of the swap method:

Press + to interact
#include <iostream>
#include<algorithm> // includes the swap function
using namespace std;
int main() {
    int x = 10, y = 20, a[2] = {30, 40};
    cout << "[Before Swap]\n";
    cout << "x: " << x << " y: " << y << "\n";
    cout << "a[0]: " << a[0] << " a[1]: " << a[1] << "\n";
    swap(x, y);
    swap(a[0], a[1]);
    cout << "\n[After Swap]\n";
    cout << "x: " << x << " y: " << y << "\n";
    cout << "a[0]: " << a[0] << " a[1]: " << a[1] << "\n";
    return 0;
}

Although the above approach is quite simple, it wouldn't work when swapping rows in a 2-D array. So, let's spin up our custom function for this task.

Swapping two rows

Sample input

Matrix 1:
                  4  3  2  1  5
                  5  2  5  4  6
                  1  2  3  5  7
                  8  9  6  3  2
                  1  3  5  7  9

Sample output

After swapping row 1 and 3
                  1  2  3  5  7
                  5  2  5  4  6
                  4  3  2  1  5
                  8  9  6  3  2
                  1  3  5  7  9

To swap two rows, we need to invoke the swap method on all of the corresponding entries of the two rows. The code snippet below provides the implementation for this:

void swapRows(int M[][maxCols], int cols, int ri, int rj)
{
  for(int ci=0; ci<cols; ci++)
    swap(M[ri][ci], M[rj][ci]);
}
The swapRows function

Since we now have a method to swap rows, let's head into the bubble sort algorithm.

Bubble sort algorithm (on matrix)

To understand the bubble sort algorithm, we first need to comprehend what sorting a column means for a matrix. Consider the following 5 x 5 matrix:

Matrix:
                  4  3  2  1  5
                  5  2  5  4  6
                  1  2  3  5  7
                  8  9  6  3  2
                  1  3  5  7  9

If we sort the last column in ascending order, it would contain the values 2 5 6 7 9 respectively. 

                  ... ... ... 2
                  ... ... ... 5
                  ... ... ... 6
                  ... ... ... 7
                  ... ... ... 9

However, the values of other columns would change since we don't swap individual elements; rather, we swap complete rows. The complete matrix after sorting the last column is shown below:

Last column sorted (Asc Order):
                  8  9  6  3  2
                  4  3  2  1  5 
                  5  2  5  4  6
                  1  2  3  5  7
                  1  3  5  7  9

The animation below depicts how the method would execute:

The code snippet below provides the bubbleSortAscBasedOnLastCol method that sorts the last column of the given matrix. It contains a nested loop that compares each row, ri, with the next row, ri+1, in the last column (cols-1). If the current row's value exceeds the next row's value, it swaps the rows. This step iterated a number of rows times to sort the column completely.

Here’s the code and testing program:

Press + to interact
main.cpp
Matrix.txt
void load2DArray(ifstream &rdr, int Array[][maxCols], int &rows, int &cols);
void print2DArray(const char MSG[], int Array[][maxCols], int rows, int cols);
void swapRows(int M[][maxCols], int cols, int ri, int rj);
// Assume we have the implementation available
void bubbleSortAscBasedOnLastCol(int M[][maxCols], int rows, int cols)
{
   for(int t=1; t<=rows; t++)
   {
      for(int ri=0; ri + 1 < rows; ri++)
      {
         if(M[ri][cols-1]>M[ri+1][cols-1])
            swapRows(M, cols, ri, ri+1);
      }
   }
}
void bubbleSortAscBasedOnColIndex(int M[][maxCols], int rows, int cols, int ci)
{
	// Exercise 1: Write code here
}
void bubbleSortDscBasedOnColIndex(int M[][maxCols], int rows, int cols, int ci)
{
	// Exercise 2: Write code here
}
int main()
{
	int Matrix[maxRows][maxCols], rows, cols;
	ifstream rdr("Matrix.txt");
	// STEP 1: Loading matrix
	load2DArray(rdr, Matrix, rows, cols);
	
	// STEP 2: Printing matrix
	print2DArray("Matrix :", Matrix, rows, cols);
	// STEP 3: Sorting matrix
	bubbleSortAscBasedOnLastCol(Matrix, rows, cols);
	/* Test your code here for any column for Exercise. On the 4th argument, 
	   write the column index based on the one you want to sort.
	*/
	// 	bubbleSortAscBasedOnColIndex(Matrix, rows, cols,???);
	/* Test your code here for any column for Exercise. On the 4th argument, 
	   write the column index based on the one you want to sort.
	*/
	// 	bubbleSortDscBasedOnColIndex(Matrix, rows, cols,???);
	// STEP 4: Printing sorted matrix
	print2DArray("Matrix Sort", Matrix, rows, cols);
	return 0;
}

Exercise 1: Matrix sort based on a particular column ci

Now change the sorting algorithm such that now the function should take a column, ci, as a parameter and sort the matrix based on that particular column.

Instruction: Write the code in the above playground.

Exercise 2: Matrix sort based on a particular column ci in descending

Now, change the sorting algorithm such that the function should take ci as a parameter and sort the matrix based on that particular column in descending order.

Instruction: Write the code in the above playground.