行と列の要素がソートされている整数の2次元配列をソートする

Question

ここで少し助けが必要です。私は行と列の要素が既に昇順。（好ましい言語C/C++）でをソートされた2次元整数配列をソートするために、私は効率的な方法 を必要割り当てをやっています。

入力：

1 5 10 15 20 
2 7 12 17 22 
4 9 18 25 28 
11 14 21 26 31 

出力：事前に

1 2 4 5 7 
9 10 11 12 14 
15 17 18 20 21 
22 25 26 28 31 

感謝。

Answer 1

がここにヒントがあります - それは型キャストの少しを使用して、通常の2次元C配列、だと仮定すると、あなたは1次元配列としてそれを解釈することができるはずです。

Answer 2

はマージソートで使用されるものと同様のマージ方法を使用して、列（または行）をマージします。各列は、それ自体でソートされているという事実を利用するだろう

。

これは十分に速いはずです。

EDIT

そしてマージ機能が標準ライブラリにすでに存在しているようです。

Answer 3

"flood fill"やA *のようなパス探索アルゴリズムに似た何らかのアルゴリズムを使用します。左上隅（値1）から開始し、それを出力し、右と下に「展開」して、その値（2と5）をリストに追加します。これらの両方とも1より大きいでしょう。あなたのリスト（値2）から最小の値を出力し、それを "展開"してください。リストに4と7が追加され、4が出力され、それを「展開」します。ソートされたリストを維持することによって、あなたは出力最小の要素が瞬時にして一度も（f.e. 10,11,12）で連続した値の出力、複数の「実行」することができるかもしれないことを

は

注意。だから、擬似コードは次のようになります。

// array a[y][x] 
// list L - ordered insertion, additionally stores matrix indices of values 
add a[0][0] to L 
loop until L is empty 
    output first element of L 
    remove first element of L and add its right and bottom neighbors (if any) to L 
loop end 

編集：ここで働いCの実装です。

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

#define COLS 5 
#define ROWS 4 

int matrix[ROWS][COLS] = { 
    1, 5, 10, 15, 20, 
    2, 7, 12, 17, 22, 
    4, 9, 18, 25, 28, 
    11, 14, 21, 26, 31 
}; 

struct entry { 
    int value; 
    int x, y; 
}; 

entry list[ROWS+COLS]; // Not sure how big the list can get, but this should be enough 
int list_len = 0; 

void set_list_entry(int index, int value, int x, int y) { 
    list[index].value = value; 
    list[index].x = x; 
    list[index].y = y; 
} 

void add_to_list(int x, int y) { 
    int val = matrix[y][x]; 
    int i, pos = list_len; 

    for (i = 0; i < list_len; i++) { 
    if (list[i].value == val) return; // Don't add value that is on the list already 
    if (list[i].value > val) { 
     pos = i; 
     break; 
    } 
    } 
    // Shift the elements after pos 
    for (i = list_len + 1; i > pos; i--) { 
    set_list_entry(i, list[i - 1].value, list[i - 1].x, list[i - 1].y); 
    } 
    // Insert new entry 
    set_list_entry(pos, val, x, y); 

    list_len++; 
} 

int main() { 
    int iteration = 0; 

    add_to_list(0,0); 

    do { 
    // output first element of list 
    printf("%i ", list[0].value); 
    iteration++; 
    if ((iteration % COLS) == 0) printf("\n"); 
    // add neighbors of first element of list to the list 
    if (list[0].x < (COLS - 1)) add_to_list(list[0].x + 1, list[0].y); 
    if (list[0].y < (ROWS - 1)) add_to_list(list[0].x, list[0].y + 1); 
    // remove first element of list 
    for (int i = 0; i < list_len; i++) { 
     set_list_entry(i, list[i + 1].value, list[i + 1].x, list[i + 1].y); 
    } 
    list_len--; 
    } while (list_len > 0); 

    return 0; 
} 

リストの長さに関するコメントに注意してください。私は、リストを取得することができますどのように大きなわからないんだけど、私はCOLS+ROWSはこの最悪のケースを見て十分なはずだと思う：

1 3 5 7 9 .. 
2 y y y y 
4 y x x x 
6 y x x x 
8 y x x x 
. 
. 

すべての「国境」の要素が最小y値未満であれば、あなたが買ってあげますプロセス内のy値の完全なリスト。(ROWS - 1) + (COLS - 1)要素です。

は、このような最悪のケースを見て、私は、これが最も効率的な解決策ではないと思いますが、私はそれはそれにもかかわらず、エレガントかつ簡潔な一つだと思います。

Answer 4

は、なぜ私たちは「Nはそれぞれ、k個の要素を持つリストをソートマージ」として、この問題を考慮していません。

k要素の最小ヒープを作成する。その最小ヒープにソートされたリストの各最小要素を配置します。ヒープの根をポップします。要素がルートであったlistの次の要素を挿入します。 このようにして、N * k log（k）の複雑さを得る。

上記の場合、Nは1行の要素数であるN^2log（N）になります。