How to sort a 2D Matrix

Question

I was asked this question in an interview. I am given a 2D array of random numbers(numbers can be repeated) and I need to sort them both row and column wise i.e. all the rows and columns should be sorted. Can anyone please explain how to do it efficiently(min time and space complexity). If you can give a code in C or C++ then that would be really helpful

Answer 1

My idea is that a 2D array can (in some cases) be considered as a 1D array because of the memory storage of it. If not, you can either copy it into a 1D array of write a custom sort function that use a function that translate the indexes from 1D to 2D.

Here an example using the function qsort:

#include <stdio.h>
#include <stdlib.h>

int matrix[4][4];

void print_matrix() {
    int i, j;
    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int compar(const void *a, const void *b) {
    int ia = *((int*)a);
    int ib = *((int*)b);
    return ia - ib;
}

int main() {
    int i, j;
    // Init of a 2D array with random numbers:
    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++) {
            matrix[i][j] = random() % 10;
        }
    }

    // Before:
    printf("Before:\n");
    print_matrix();

    // This array can be considered as a big 1D array.
    qsort(matrix, 16, sizeof(int), compar);

    // After:
    printf("After:\n");
    print_matrix();

    return 0;
}

Output:

Before:
3 6 7 5 
3 5 6 2 
9 1 2 7 
0 9 3 6 
After:
0 1 2 2 
3 3 3 5 
5 6 6 6 
7 7 9 9 

Edit: OP asked me to avoid using qsort... So here a quicksort able to sort a 2D array:

#include <stdio.h>
#include <stdlib.h>

void print_matrix(int **matrix, int rows, int cols) {
    int i, j;
    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

void swap(int *a, int *b) {
    int buf = *a;
    *a = *b;
    *b = buf;
}

int partition(int **a, int l, int r, int c) {
    int i;
    // Left pivot
    int pivot_val = a[l/c][l%c];
    // Move pivot to end
    swap(&a[l/c][l%c], &a[r/c][r%c]);

    // If <= to the pivot value, swap
    int j = l;
    for (i = l; i < r; i++) {
        if (a[i/c][i%c] <= pivot_val) {
            swap(&a[i/c][i%c], &a[j/c][j%c]);
            j++;
        }
    }

    // Move pivot to its place.
    swap(&a[j/c][j%c], &a[r/c][r%c]);

    return j;
}

void quicksort_r(int **a, int l, int r, int c) {
    if (l < r) {
        int pivot = partition(a, l, r, c);
        quicksort_r(a, l, pivot-1, c);
        quicksort_r(a, pivot+1, r, c);
    }
}

void quicksort(int **a, int rows, int cols) {
    quicksort_r(a, 0, rows * cols - 1, cols);
}

int main() {
    int i, j;
    int rows = 5;
    int cols = 4;
    int **matrix = malloc(sizeof(int*) * rows);

    // Init of a 2D array with random numbers:
    for (i = 0; i < rows; i++) {
        matrix[i] = malloc(sizeof(int) * cols);
        for (j = 0; j < cols; j++) {
            matrix[i][j] = random() % 10;
        }
    }

    // Before:
    printf("Before:\n");
    print_matrix(matrix, rows, cols);

    quicksort(matrix, rows, cols);

    // After:
    printf("After:\n");
    print_matrix(matrix, rows, cols);

    return 0;
}

Which gives:

Before:
3 6 7 5 
3 5 6 2 
9 1 2 7 
0 9 3 6 
0 6 2 6 
After:
0 0 1 2 
2 2 3 3 
3 5 5 6 
6 6 6 6 
7 7 9 9 

Edit2: I realized afterward that there is another obvious solution for square matrices:

Let's take the first example:

0 1 2 2 
3 3 3 5 
5 6 6 6 
7 7 9 9

There is also:

0 3 5 7
1 3 6 7
2 3 6 9
2 5 6 9

But for the second example too:

0 0 1 2 
2 2 3 3 
3 5 5 6 
6 6 6 6 
7 7 9 9 

And:

0 2 3 6
0 2 5 6
1 3 5 6
2 3 6 6
7 7 9 9

Which means that maybe we could do a specialized algorithm able to give all the solutions or an algorithm that tries to minimize the number of moves, I don't know. It's a quite interesting problem in fact.

Answer 2

Try using and adapting this...

void sort(int MyArray[8][8])
{
     for(int ir=0;ir<8;ir++)
     {
        for(int ic=0;ic<8;ic++)
        {
            for(int jr=0;jr<8;jr++)  
            {
                    for(int jc=0;jc<8;jc++)
                    {        
                      if(MyArray[ir][jr]>MyArray[ic][jc])
                       {
                         int temp=MyArray[ir][jr];
                         MyArray[ir][jr]=MyArray[ic][jc];
                         MyArray[ic][jc]=temp;
                       }
                    }
             }
        }
     }
}

This is a simple bubble sort. It effectively runs on O(n^4) You can get more effective by writing an algorithm such as quicksort. I have never seen or even thought of attempting a quicksort on a 2D array. it is not going to be easy. What you can try is adding everything into a single array, quicksort it and copy everything back into a 2D array. but the array has to be very large before it will be more effective... If someone does give a quicksort or merge sort algorithm here for a 2D array. He deserves a Medal! that is hardcore