如何对2D矩阵进行排序 [英] How to sort a 2D Matrix
问题描述
在一次采访中有人问我这个问题.我得到了一个随机数的二维数组(数字可以重复)，我需要按行和列对它们进行排序，即所有行和列都应该排序.谁能解释一下如何有效地做到这一点(最小的时间和空间复杂度).如果您可以用C或C ++编写代码，那将真的很有帮助
I was asked this question in an interview. I am given a 2D array of random numbers(numbers can be repeated) and I need to sort them both row and column wise i.e. all the rows and columns should be sorted. Can anyone please explain how to do it efficiently(min time and space complexity). If you can give a code in C or C++ then that would be really helpful
推荐答案
我的想法是，由于2D数组的内存存储，在某些情况下可以将其视为1D数组.如果没有，则可以将其复制到一维数组中，然后编写一个自定义排序函数，该函数使用将索引从1D转换为2D的函数.
My idea is that a 2D array can (in some cases) be considered as a 1D array because of the memory storage of it. If not, you can either copy it into a 1D array of write a custom sort function that use a function that translate the indexes from 1D to 2D.
下面是使用qsort函数的示例:
Here an example using the function qsort:
#include <stdio.h>
#include <stdlib.h>
int matrix[4][4];
void print_matrix() {
int i, j;
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}
int compar(const void *a, const void *b) {
int ia = *((int*)a);
int ib = *((int*)b);
return ia - ib;
}
int main() {
int i, j;
// Init of a 2D array with random numbers:
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
matrix[i][j] = random() % 10;
}
}
// Before:
printf("Before:\n");
print_matrix();
// This array can be considered as a big 1D array.
qsort(matrix, 16, sizeof(int), compar);
// After:
printf("After:\n");
print_matrix();
return 0;
}
输出:
Before:
3 6 7 5
3 5 6 2
9 1 2 7
0 9 3 6
After:
0 1 2 2
3 3 3 5
5 6 6 6
7 7 9 9
OP要求我避免使用qsort ...因此这里是一种能够对2D数组进行排序的quicksort:
OP asked me to avoid using qsort... So here a quicksort able to sort a 2D array:
#include <stdio.h>
#include <stdlib.h>
void print_matrix(int **matrix, int rows, int cols) {
int i, j;
for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}
void swap(int *a, int *b) {
int buf = *a;
*a = *b;
*b = buf;
}
int partition(int **a, int l, int r, int c) {
int i;
// Left pivot
int pivot_val = a[l/c][l%c];
// Move pivot to end
swap(&a[l/c][l%c], &a[r/c][r%c]);
// If <= to the pivot value, swap
int j = l;
for (i = l; i < r; i++) {
if (a[i/c][i%c] <= pivot_val) {
swap(&a[i/c][i%c], &a[j/c][j%c]);
j++;
}
}
// Move pivot to its place.
swap(&a[j/c][j%c], &a[r/c][r%c]);
return j;
}
void quicksort_r(int **a, int l, int r, int c) {
if (l < r) {
int pivot = partition(a, l, r, c);
quicksort_r(a, l, pivot-1, c);
quicksort_r(a, pivot+1, r, c);
}
}
void quicksort(int **a, int rows, int cols) {
quicksort_r(a, 0, rows * cols - 1, cols);
}
int main() {
int i, j;
int rows = 5;
int cols = 4;
int **matrix = malloc(sizeof(int*) * rows);
// Init of a 2D array with random numbers:
for (i = 0; i < rows; i++) {
matrix[i] = malloc(sizeof(int) * cols);
for (j = 0; j < cols; j++) {
matrix[i][j] = random() % 10;
}
}
// Before:
printf("Before:\n");
print_matrix(matrix, rows, cols);
quicksort(matrix, rows, cols);
// After:
printf("After:\n");
print_matrix(matrix, rows, cols);
return 0;
}
哪个给:
Before:
3 6 7 5
3 5 6 2
9 1 2 7
0 9 3 6
0 6 2 6
After:
0 0 1 2
2 2 3 3
3 5 5 6
6 6 6 6
7 7 9 9
Edit2:之后，我意识到平方矩阵还有另一个明显的解决方案:
I realized afterward that there is another obvious solution for square matrices:
让我们举一个例子:
0 1 2 2
3 3 3 5
5 6 6 6
7 7 9 9
还有:
0 3 5 7
1 3 6 7
2 3 6 9
2 5 6 9
但是对于第二个示例:
0 0 1 2
2 2 3 3
3 5 5 6
6 6 6 6
7 7 9 9
并且:
0 2 3 6
0 2 5 6
1 3 5 6
2 3 6 6
7 7 9 9
这意味着我们也许可以做一个能够给出所有解决方案的专门算法，或者尝试使移动次数最小化的算法，我不知道.实际上，这是一个非常有趣的问题.
Which means that maybe we could do a specialized algorithm able to give all the solutions or an algorithm that tries to minimize the number of moves, I don't know. It's a quite interesting problem in fact.
这篇关于如何对2D矩阵进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
