Sorting 2D array

Question

In 2D array sorting as i seen they just copied it to single dimension array and sorted it. But is there any other way to sort 2 dimensional array without using 1D array.

// code

#include<iostream>
#include<conio.h>

using namespace std;

int main()
{
int rows, columns;
int k = 0, temp;
int rowColumn;

//getting rows and columns number
cout<<"Enter number of rows";
cin>>rows;
cout<<"Enter number of columns";
cin>>columns;

//declaring and intitalizing oneD and twoD array
rowColumn = rows * columns;
int arr[rows][columns];
int oneDArr[rowColumn];

//Fill 2D array by user
cout<<"Fill 2D array row wise"<<endl;
for(int i=0; i<rows; i++)
{
    for(int j=0; j<columns; j++)
    {
        cin>>arr[i][j];
    }
}

//Taking 2d array in 1d array
for(int i=0; i<rows; i++)
{
    for(int j=0; j<columns; j++)
    {
        oneDArr[k] = arr[i][j];
        k++;
    }
}

//Bubble sort perform on 1d array
for(int j=1;j<rowColumn;j++)
{
    for(int i=0; i<rowColumn; i++)
    {
        if(oneDArr[i]>oneDArr[i+1])
        {
            temp=oneDArr[i];
            oneDArr[i] = oneDArr[i+1];
            oneDArr[i+1]=temp;
        }
    }
}

//rearranging the oneD array to twoD array
k = 0;
for(int i=0; i<rows; i++)
{
    for(int j=0; j<columns; j++)
    {
        arr[i][j] = oneDArr[k];
        k++;
    }
}

//Displaying sorted 2d Array
for(int i=0; i<rows; i++)
{
    for(int j=0; j<columns; j++)
    {
        cout<<arr[i][j]<<"\t";
    }
    cout<<"\n";
} 
} 

Is there any other way to sort 2D array with efficiency.

Answer 1

You could use some mechanism to treat your 2d array as 1d array and this will save you extra space. If you have a an integer p,you can extract row number and column number as follows

 rownumber=p/columnsize;
 columnnumber=p%columnsize;

following is an implementation of bubble sort using the above

   #include <iostream>
   using namespace std;
   #define colsize 3
   #define rowsize 2
   int main() 
   {
      int arr[rowsize][colsize]={{7,8,9},{3,2,1}};
      int r,c,r2,c2;
      int n=rowsize*colsize;
      for(int i=0;i<n;i++)
      {
         for(int j=0;j<n-i-1;j++)
         {
            r=j/colsize;
            c=j%colsize;
            r2=(j+1)/colsize;
            c2=(j+1)%colsize;
            if(arr[r][c]>arr[r2][c2])
            {
               swap(arr[r][c],arr[r2][c2]);
            }
          }
       }
       for(int i=0;i<rowsize;i++)
       {  
           for(int j=0;j<colsize;j++)
            {
               cout<<arr[i][j]<<" ";
            }
        }
       return 0;
   }

Answer 2

If you want to sort a 2D array as if it were a 1D array (interpreted row-first or column-first) there's no real need to physically copy it to an 1D array first.

You can always pretend that you already have an imaginary 1D array, whose indices i are mapped to the indices of the original 2D array through the following formulas

i_row = i / columns;
i_column = i % columns;

Now you can simply use any 1D sorting algorithm on 1D indices, and every time you need to access element i of the imaginary 1D array, you simply calculate i_row and i_column and access the corresponding 2D element instead.

That would implement exactly the same thing as you have in your original code, but without a physical 1D array and without copying data back and forth between 1D and 2D arrays.