c - O(n) 時間での 2 次元配列の並べ替え

Question

インタビューで、2 次元配列を O(n) 時間でソートすることについて質問されました。O(n) 時間でそれを行うにはどうすればよいですか。誰かがそれに光を当てることができますか..ありがとう.

入力：

3 5 7 1
4 9 2 0
9 3 6 2   

出力

0 1 2 2 
3 3 4 5  
6 7 9 9

Answer 1

2 次元配列が実際に何を意味するのかはわかりませんが、O(n) を達成できるいくつかの状況に固有の並べ替えアルゴリズムがあります。その例はCounting sortです。1 から 1000 の範囲の 1000 個の整数を含む配列をソートする場合、O(n) でソートできます。

編集:多次元配列であるという事実は、並べ替えのロジックを変更しません。次のように、インデックスを (並べ替えを使用して) 二次元インデックスに変換できます。

array[i / N][i % N];

ここで、N は最初の次元のサイズです。

Answer 2

プレーン配列としてソートできます。
例えば

#include <stdio.h>
#include <stdlib.h>


int cmp(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}

#define ROW_SIZE 3
#define COL_SIZE 4

int main(void){
    int M[ROW_SIZE][COL_SIZE]={{3,5,7,1},{4,9,2,0},{9,3,6,2}};
    int c,r,*p;

    for(p=&M[0][0],r=0;r<ROW_SIZE;++r){
        for(c=0;c<COL_SIZE;++c){
            printf("%d ",*p++);
        }
        printf("\n");
    }
    printf("\n");
    qsort(&M[0][0], ROW_SIZE*COL_SIZE, sizeof(int), cmp);
    for(p=&M[0][0],r=0;r<ROW_SIZE;++r){
        for(c=0;c<COL_SIZE;++c){
            printf("%d ",*p++);
        }
        printf("\n");
    }

    return 0;
}