C#のジャグ配列で、配列の要素を維持したまま合計値でソートすることは可能ですか？

Question

###前提・実現したいこと
C#でジャグ配列を作り、一次元目の要素の合計値で二次元目の要素をソートしたいのですが、ソートした後に一次元目の要素を使いたいです。
今コンソールに表示されている例で言えば、Gene[0][]の合計が7、Gene[1][]の合計が5、Gene[2][]の合計が7、Gene[3][]の合計が6なので、配列の二次元目を{0,2,3,1}というようにソートし、上位二つであるGene[0][]の要素とGene[2][]の要素を後で使用したいです。
なので一次元目の要素を維持したまま一次元目の要素の合計値で二次元目の要素をソートする方法を探しています。そのようなことは可能でしょうか？

###コンソールの表示

Gene[0]
0111010111
Gene[1]
0110010011
Gene[2]
0111101011
Gene[3]
1011101001

###該当のソースコード

class Run
{
　　public static void Main()
    {
        Random rnd = new Random();
        int[][] Gene;

        for (int i = 0; i < 4; i++)
        {
            Gene = new int[4][];
            Gene[i] = new int[10];
            for (int j = 0; j < 10; j++)
            {
                Gene[i][j] = rnd.Next(0, 2);
            }
            Console.WriteLine("Gene[{0}]", i);
            foreach (int ge in Gene[i])
            {
                Console.Write(ge);
            }
            Console.WriteLine();
        }
    }
}

###試したこと
Array.Sortを試してみましたが、ジャグ配列でそのまま使うとエラーになるんですね…

Answer 1

配列の二次元目を{0,2,3,1}というようにソートし

説明を読むと少し混乱しましたが、次のような並び替えをするというふうに解釈しました。

before        => after
Gene[0]      
A:0111010111     A:...
Gene[1]
B:0110010011     C:...
Gene[2]
C:0111101011     B:...
Gene[3]
D:1011101001     D:...

もしそうでないなら本回答はスルーしてください。もし上の通りなら「配列の一次元目をソート」と表現するのが普通な気がします。

さて、上記を前提と考えるならこれは普通のソートと言えると思います。LinqでもArray.Sortでも実現できますが、とりあえず「ソートできればよい」という前提での例を挙げますと・・・

// Linq
int[][] sorted = Gene.OrderByDescending(row => row.Sum()).ToArray();

// Array.Sort

int[] keys = Gene.Select(row => -row.Sum()); // (1)
Array.Sort(keys, Gene);

// なお(1)は概ね以下のような処理を表しています。
int[] keys = new int[Gene.Length]; // int[]を生成すると初期値は0であることが保証されている
for (int i = 0; i < keys.Length; i++) {
  foreach (int e in Gene[i]) keys[i] -= e;
}

LinqのOrderByはキーの計算を各々の要素に対して1度しかしないのでキーの計算量が大きくても非効率とはならず、一次元目の構造を再構築する関係でメモリー消費量が多めにかかるという感じだと思います。また安定ソートなのですね。今回初めて知りました。

上のArray.Sortはkey配列を使う例です。他にComparison<int[]>, IComparer<int[]>を使うパターンもありますが、それらは比較する回数だけキー計算が必要になりキー計算量が大きい場合は不利ですので上の例の方が早い気がします。なおArray.Sortは安定ソートではないそうです。単純なクイックソートを採用しているのかも知れません。

速度とメモリー消費量、安定ソートかどうかなどについては研究してみるとよいと思います。自分の場合は巨大な配列をソートすることなどないのでもっぱらLinqでよいと考える方です。要素数のオーダーが数千・数万になる場合は一応調べてから選ぶかも知れません・・・

Comments

[rinmeda317]

深夜にもかかわらず丁寧な回答ありがとうございます。
その解釈で合っています。
当方C#は初心者なのでLinqはよくわからず、Array.Sortを使ってみようと思ったのですが、例をそのまま入れてみたらエラーになりました…
エラーメッセージは「'int[][]' does not contain a definition for 'Select' and no extension method 'Select' accepting a first argument of type 'int[][]' could be found (are you missing a using directive or an assembly reference?) (CS1061)」と「 Use of unassigned local variable 'Gene' (CS0165)」でした。

[KSwordOfHaste]

多分
using System.Linq;
としていないからではないでしょうか。
ーーーちょっと補足します。Array.Sortの例でkeysを求めるのにLinqを使っているのです。Linqを使わずに単純にforループで作ってもよいと思います。そういう例にした方がわかりやすかったかも知れませんね。

[rinmeda317]

初歩的な質問で申し訳ないのですが、
foreach (int e in Gene[i]) keys[i] -= e;
この行の処理がどうなっているのか教えていただけないでしょうか。

また、for文の外にこのスクリプトを書く場合、変数Geneの呼び出しが必要みたいなのですが呼び出し方がよくわかりません。

[KSwordOfHaste]

i行目の全てのデータをkeys[i]から減算するという意味です。
for文など基本的な文法は別途しっかり確認してくださいね！

＞変数Geneの呼び出しが・・・
自分はソートする部分のみコードを挙げたのです。全体はご自分で考えてみてほしいです。

[rinmeda317]

失礼しました。
何日も考えていてもうまくいかず自信喪失していたみたいです。
本をまた読み返して考えてみるとします。
付き合ってくださってありがとうございました。

[KSwordOfHaste]

コード自体は少しデバッグをすれば動きそうな雰囲気に見えます。ここでひと踏ん張りするのが上達のコツだと思います。1点だけ指摘しておきましょう。
Gene = new int[4][];
はそれを囲むfor文の外側でやらないといけません。Geneを宣言している行で下記のように同時に初期値を代入するのがよいと思います。
int[][] Gene = new int[4][];

[rinmeda317]

言われてみればGene = new int[4][];をfor文の中で宣言しなければいけない理由はありませんね…ありがとうございます。

[rinmeda317]

おかげさまで、遺伝的アルゴリズムのOneMax問題のスクリプトを完成させることができました。本当にありがとうございます！！