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.

You could set up a method of accessing the 2D array such that the 1D algorithm can work on it seamlessly. Mostly, you can use any of the many sort algorithms which improve upon bubble sort. — Politank-Z, Jun 30 '15 at 17:39
possible duplicate of [C Array sorting tips](http://stackoverflow.com/questions/3893937/c-array-sorting-tips) — Toumash, Jun 30 '15 at 17:41
@Politank-Z - If you're guaranteed that the array's storage is contiguous, that would be relatively trivial. — Mr. Llama, Jun 30 '15 at 17:51
First, you have to explain what you mean by "sorting of 2D array". There are many completely different understandings of such sorting. There's no point in discussing *how* to do something, when it is not clear *what* you are trying to do. — AnT stands with Russia, Jun 30 '15 at 17:56
@Mr.Llama Even if you aren't so guaranteed, and you know the width of your array, you are still in spitting distance of trivial. — Politank-Z, Jun 30 '15 at 17:56

AnT stands with Russia · Answer 1 · 2015-06-30T18:05:16.850

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.

Gaurav Sehgal · Accepted Answer · 2015-06-30T18:06:18.913

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;
   }

yeah that's not required. – Gaurav Sehgal Jun 30 '15 at 18:03 — Gaurav Sehgal, Jun 30 '15 at 18:03

Sorting 2D array

2 Answers2