Linear Sort of a 2D Array

I am a newb开发者_开发百科ie to C programming and was trying to prepare some sorting programs. I made the program of linear/ normal Sorting.

Now I want to make a program to sort 2D array. i.e. If the matrix is

4  6  1
3  2  9
5  7  8

Then the result should be

1  2  3
4  5  6
7  8  9

Since you want your 2D array to be sorted row-wise, which happens to be the order in which multidimensional arrays are stored in C, you could pretend it is a 1D array and sort it that way.

Assuming you have a function void sort(int[], int size); that takes a pointer to the first element of a 1D array and its size, you could do

int a[3][3] = {{4,6,1}, {3,2,9}, {5,7,8}};
sort(&a[0][0], 9);

Naturally, this only works for true 2D arrays, not for arrays of pointers, which is how dynamically allocated 2D arrays are often implemented in C.

You can use pretty much the same function, if you are allocating the memory as a regular multi-dimensional declaration... Since multi-dimensional arrays are stored in memory row after row and each row is just a regular array.

Just pass to the function the address of the first element of the matrix (usually name_of_the_matrix[0]) and the number of elements in the matrix.

Hope I could help.

The basic idea is to sort the array based on cell ordering, so you need to have a way to get a cell based on it's order and a way to write a cell based on it's ordering.

int getCellOrder(int x, int y) {
   return x*(x_width) + y;
}

int getXpos(int cellOrder) {
   return cellOrder / x_width;
}

int getYpos(int cellOrder) {
   return cellOrder % x_width;
}

With those two elements, you can now grab any two cell orders for your array, and the values they reference.

int valueAt(int cellOrder) {
   return array[getXpos(cellOrder)][getYpos(cellOrder];
}

How you compare the orders and how you swap them now becomes a simple 1D array problem.

you can use Bubble-Sort: Wikipedia and go through the array with a for-loop.

You could also take the C++ approach and do the following while representing your matrix in 1D:

#include <vector>
#include <algorithm>
using namespace std;

int main(int arg, char **argv) {
  int matrix[] = {4, 6, 1, 3, 2, 9, 5, 7, 8};
  vector<int> matvec (matrix, matrix + sizeof(matrix) / sizeof(int));
  sort(matvec.begin(), matvec.end());
  return 0;
}

I made it like this given that you made an 2D array a[][] and the elements like me:

for(i=0;i<row;i++)
 for(j=0;j<col;j++)
  for(k=0;k<row;k++)
   for(p=0;p<col;p++)
      if(a[i][j]>a[k][p])
      temp=a[i][j]; a[i][j]=a[k][p]; a[k][p]=temp;