Problem Solving: Sorting Huge Numbers

Learn how multi-dimensional arrays can be used to represent big numbers and they can be manipulated like sorting.

We'll cover the following

Radix sort on a matrix

Consider an m x n matrix where each row constitutes a complete number. For example, take a look at the 5 x 5 matrix below:

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

For the matrix above, the first row represents the number, 43215, the second row represents the number, 52546, and so forth. The radix sort algorithm arranges these numbers in an ascended or descended manner inside the matrix.

Algorithm

The following is a list of steps to perform a radix sort on an m x n matrix where each row represents a single number:

  1. Select a column. Initially, we select the least significant column. Then, we move towards the left (more significant figure).

  2. Apply row-based bubble sorting on the selected column.

    • In row-based bubble sorting, we compare two neighboring numbers in a specific column. If the first number is greater than the second, we swap both rows for ascending sort. This is repeated until the column is completely sorted.

  3. Repeat the first two steps for each column from right to left.

The illustration below provides the summary of the above algorithm:

Implementation

We'll leverage the row-based bubble sorting bubbleSortBasedOnColIndex we created in the previous lesson to implement the radix sort algorithm.

This method takes the matrix with dimensions and the column's index to sort. It utilizes the swapRows method to sort the specified column. The playground below provides signatures of both these methods; feel free to implement these to test yourself.

Press + to interact
#include <iostream>
using namespace std;
#define maxRows 100
#define maxCols 100
void swapRows(int M[][maxCols], int cols, int ri, int rj)
{
    // Write your implementation here
}
void bubbleSortBasedOnColIndex(int M[][maxCols], int rows, int cols, int ci)
{
    // Write your implementation here
}

Before we head into the implementation, let's observe the radix sort animation below:

From the animation above, it's pretty clear that all we have to do is to invoke bubbleSortBasedOnColIndex iteratively on each column starting from the rightmost (least significant digit) to the leftmost (most significant digit). So, let's quickly spin up a matrixSort method that does this job for us.

void radixSort(int M[][maxCols], int rows, int cols)
{
    for(int ci=cols-1; ci>=0; ci--)
        bubbleSortBasedOnColIndex(M, rows, cols, ci);
}
The matrixSort function

The radixSort method takes in the matrix and its dimensions and calls the bubbleSortBasedOnColIndex() function in each iteration of the for loop by passing the current column index, ci, to the method. Since the loop starts at cols-1 and decrements by one after each iteration, our matrix gets completely sorted.

Finally, we have also provided the complete implementation of the radix sort algorithm below:

5 5
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
Radix sort

Now, we'd like you to complete the following two exercises. If you get stuck, feel free to look at the solution. Best of luck!

Exercise 1: Selection sort

Write code for the selection sort algorithm and perform the same sorting on the matrix as we have done above using the bubble sort algorithm. We have discussed the idea and implementation of selection sort in this lesson.

Your implementation

5 5
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
Radix sort using selection sort

Exercise 2: Sorting column numbers

Change the program above such that every column represents a number, i.e., a matrix of m x n is equivalent to n numbers, each having m digits. Refer to the sample program output below for clarification:

Your implementation

Press + to interact
main.cpp
Numbers.txt
void swapCols(int M[][maxCols], int rows, int ci, int cj)
{
    // Write your code here
}
void bubbleSortBasedOnRowIndex(int M[][maxCols], int rows, int cols, int ri)
{
    // Write your code here
}
void matrixSort(int HugeNumbers[maxRows][maxCols], int rows, int cols)
{
    // Write your code here
}
int main()
{
	int HugeNumbers[maxRows][maxCols], 
        rows, cols;
	ifstream rdr("Numbers.txt");
	// STEP 1: Loading matrix
	load2DArray(rdr, HugeNumbers, rows, cols);
	cout << "rows:"<<rows<<" cols:"<<cols<<endl;
	// STEP 2: Printing matrix
	print2DArray("HugeNumbers (Before sorting):", HugeNumbers, rows, cols);
	// STEP 3: Sorting matrix
	matrixSort(HugeNumbers, rows, cols);
	// STEP 4: Printing sorted matrix
	print2DArray("HugeNumbers ( After sorting):", HugeNumbers, rows, cols);
/*. Expected output
      12345
      45256
      53217
      36982
      75319
*/
	return 0;
}

Great job on completing the lesson! We hope you were able to do the exercises by yourself.