# Problem Solving: Matrix Sorting

Learn how to sort multi-dimensional arrays.

## 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:

#include <iostream>#include<algorithm> // includes the swap functionusing 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]);}

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:

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 availablevoid 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 matrixload2DArray(rdr, Matrix, rows, cols);// STEP 2: Printing matrixprint2DArray("Matrix :", Matrix, rows, cols);// STEP 3: Sorting matrixbubbleSortAscBasedOnLastCol(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 matrixprint2DArray("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.