Linear Sort of a 2D Array in C

问题:

I am a newbie 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

Please help me finding some logic about such programs.

回答1:

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.

回答2:

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.

回答3:

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.

回答4:

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

回答5:

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

回答6:

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;