Print Elements in Sorted Order using Row-Column Wise Sorted Matrix in C

April 30, 2022

Print Elements in Sorted Order using row-column wise sorted matrix in C

Here, in this page we will discuss the program to print elements in sorted order using row-column wise sorted matrix in C programming language. We are given with a matrix in which each row and column are sorted in non-decreasing manner.

Print Elements in Sorted Order using row-column wise sorted matrix in C

Method Discussed :

  • Method 1 : Using extra space.
  • Method 2 : Without using extra space.

Method 1 :

  • Let’s say the number of rows be n and number of columns be m.
  • Now, create an array of size (n*m).
  • Insert all the elements of the matrix in the declared array.
  • Using sort() function sort the entire array.
  • Print the array.

Time and Space Complexity :

  • Time-Complexity : O(n*m*log(n*m))
  • Space-Complexity : O(n*m)

Method 1 : Code in C

Run 
#include <stdio.h>

int main(){

   int n=4, m=4;
   int mat[4][4]= { { 1, 20, 43, 14 },
                    { 50, 69, 17, 81 },
                    { 99, 10, 11, 22 },
                    { 13, 54, 95, 16 } };

   int arr[16], x=0;

   for(int i=0; i< n; i++){
       for(int j=0; j< m; j++){
            arr[x++]=mat[i][j];
       }
    }

    int size = n*m;
    
    for(int i=0; i< size; i++){
        for(int j=i+1; j< size; j++){
            if(arr[i]>arr[j]){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
   for(int i=0; i< size; i++)
        printf("%d ",arr[i]);
}
Output
1 10 11 13 14 16 17 20 22 43 50 54 69 81 95 99

Method 2 :

  • Let’s say the number of rows be n and number of columns be m.
  • Now, create a recursive function which takes n arrays and returns the output array.
  • In the recursive function, if the value of n is 1 then return the array else if the value of n is 2 then merge the two arrays in linear time and return the array.
  • If the value of n is greater than 2 then divide the group of n elements into two equal halves and recursively call the function, i.e 0 to n/2 array in one recursive function and n/2 to n array in another recursive function.
  • Print the array.

Time and Space Complexity :

  • Time-Complexity : O(n*m*log(m))
  • Space-Complexity : O(n*m*log(m))

Method 2 : Code in C

Run 
#include <stdio.h>

#define n 4

void mergeArrays(int arr1[], int arr2[], int n1, int n2, int arr3[]) 
{ 
    int i = 0, j = 0, k = 0; 

    while (i < n1 && j < n2){ 
       if (arr1[i] < arr2[j]) 
         arr3[k++] = arr1[i++]; 
       else
         arr3[k++] = arr2[j++]; 
    } 

    while (i < n1) 
        arr3[k++] = arr1[i++]; 

    while (j < n2) 
        arr3[k++] = arr2[j++]; 
}

void mergeKArrays(int arr[][n], int i, int j, int output[])
{
    if(i==j)
    {
      for(int p=0; p < n; p++)
       output[p]=arr[i][p];
      return;
     }

     if(j-i==1)
     {
       mergeArrays(arr[i],arr[j],n,n,output);
       return;
     }

     int out1[n*(((i+j)/2)-i+1)],out2[n*(j-((i+j)/2))];

     mergeKArrays(arr,i,(i+j)/2,out1);
     mergeKArrays(arr,(i+j)/2+1,j,out2);
     mergeArrays(out1,out2,n*(((i+j)/2)-i+1),n*(j-((i+j)/2)),output);

}

int main()
{
    int arr[][n] = {{2, 6, 12, 34},{10, 19, 20, 1000},{23, 34, 90, 2000}};
    int k = sizeof(arr)/sizeof(arr[0]);
    int output[n*k];
    mergeKArrays(arr,0,2, output);

    for (int i=0; i < 12; i++)
     printf("%d ", output[i]);

    return 0;
}
Output
2 6 10 12 19 20 23 34 34 90 1000 2000
While loop in C