【C#】２次元配列（ジャグ配列・多次元配列）のソート

【C#】２次元配列（ジャグ配列・多次元配列）のソート　[⇒PCページへ]

2016年12月05日23:38 C#

　C#には「ジャグ配列」と「多次元配列」があるのだが、結論を先に言ってしまうと、ソートするならジャグ配列の方が簡単である。というのは初めから用意されている方法が色々あるからだ。では多次元配列はどうかというと、特に用意はされていないので自作することになる。なので、標準的な機能と一般的なソートアルゴリズムとを使って、いくつかの方法でソートをやってみよう。

■ジャグ配列でのソート (ラムダ式)
■ジャグ配列でのソート (LINQ)
■ジャグ配列でのソート (IComperer, IComparable)
■多次元配列でのソート (クイックソート)
■多次元配列でのソート (挿入ソート)
■多次元配列→ジャグ配列変換してソート
■キーと値の２つの配列でのソート

■ジャグ配列でのソート

　まずジャグ配列の動作を確認しておこう。ジャグ配列とは配列の入れ子状態で、「親の次元は子の次元のオブジェクトの参照を持っている」と考えれば良い。今回の場合２次元配列なので、一番親の配列はそれぞれの配列の参照を格納にしている感じになる。つまりその参照を交換すれば１行分のデータ（配列）を交換したことと同じことになる。図のように考えた場合、縦方向のソート（列をキーに行をソート）となることがわかる。これは他の言語でもだいたい同じなので、覚えておくと色々と応用が利く。

●ジャグ配列でのソート (ラムダ式)

using System;
using System.Text;

//ジャグ配列
int[][] jag = {
    new int[] {0, 1, 200},
    new int[] {1, 3, 100},
    new int[] {2, 4, 100},
    new int[] {3, 2, 300},
    new int[] {4, 0, 200},
};

Array.Sort(jag, (a, b) => a[1] - b[1]);  //昇順(index=1)

Console.WriteLine(ToString(jag));  //デバッグ用関数（※下記を参照）

[[4, 0, 200],
[0, 1, 200],
[3, 2, 300],
[1, 3, 100],
[2, 4, 100]]

(※) ToString(T[][]) は前回作った関数を参照（配列の内容を文字列化→表示するだけのもの）

　ラムダ式の書き方だといまいちアルゴリズムがわかりずらいが、やっていることは上の図と同じと考えて良いだろう。もっとコードの意味を知りたいなら、以下に示す「Comparer」での書き方の方がわかりやすい。実行速度などの違いはあるかもしれないが、ラムダ式だと簡潔に書けることが利点だ。

　ちなみに、ソート第２キーを加えたいなら、ソート関数部分を次のように書くこともできる。これも「Comparer」での書き方と比較すると意味がわかりやすい。用途によって書き分けると良いだろう。

Array.Sort(jag, (a, b) => a[2] == b[2] ? a[1] - b[1] : b[2] - a[2]);  //降順(index=2), 昇順(index=1)

[[3, 2, 300],
[4, 0, 200],
[0, 1, 200],
[1, 3, 100],
[2, 4, 100]]

　これはインデクス[2]の列は降順に、インデクス[1]の列は昇順にしてソートしている（ソート第１キー：[2]が同じなら、ソート第２キー：[1]でソートする）。

●ジャグ配列でのソート (LINQ)

using System;
using System.Linq;

//ジャグ配列
var jag = new [] {
    new [] {0, 1, 200},
    new [] {1, 3, 100},
    new [] {2, 4, 100},
    new [] {3, 2, 300},
    new [] {4, 0, 200},
};

var sorted = jag.OrderBy(e => e[1]);  //昇順(index=1)

foreach (var s in sorted) {
    foreach (var e in s) {
        Console.Write(e + ", ");
    }
    Console.WriteLine();
}

4, 0, 200,
0, 1, 200,
3, 2, 300,
1, 3, 100,
2, 4, 100,

　これは先の例のラムダ式と同じ結果となる。型を必要としないなら、この方法でも良いだろう。「using System.Linq」が必要なので忘れずに。

　ちなみに、降順なら「OrderByDescending」を使う。また、「OrderBy～」で同じ値になる場合は「ThenBy/ThenByDescending」で順をつけることができる。つまり第２キーを加えたいなら、以下のようにする。

var sorted = jag.OrderByDescending(e => e[2]).ThenBy(e => e[1]);  //降順(index=2), 昇順(index=1)

3, 2, 300,
4, 0, 200,
0, 1, 200,
1, 3, 100,
2, 4, 100,

●ジャグ配列でのソート (IComparer, IComparable)

using System;
using System.Collections.Generic;
using System.Text;

//比較クラス（比較関数）
public class MyComparer<T> : IComparer<T[]> where T : IComparable
{
    public int Compare(T[] a, T[] b)  {
        return a[1].CompareTo(b[1]);  //昇順
        //return b[1].CompareTo(a[1]);  //降順
    }
}

public static void Main()
{
    //ジャグ配列
    int[][] jag = {
        new int[] {0, 1, 200},
        new int[] {1, 3, 100},
        new int[] {2, 4, 100},
        new int[] {3, 2, 300},
        new int[] {4, 0, 200},
    };

    Array.Sort(jag, new MyComparer<int>());

    Console.WriteLine(ToString(jag));  //デバッグ用関数（※下記を参照）
}

[[4, 0, 200],
[0, 1, 200],
[3, 2, 300],
[1, 3, 100],
[2, 4, 100]]

(※) ToString(T[][]) は前回作った関数を参照（配列の内容を文字列化→表示するだけのもの）

　「Comparer」「IComparer」「IComparable」と同じようなものが並んでいてややこしいが、「Comparer」は IComparer などを実装しているクラス、「IComparer」は「Compare()」（比較関数）を使うためのインターフェース、「IComparable」は「CompareTo()」（大小関係を返す関数）を使うためのインターフェースと覚えておけば良いだろう。比較関数は基本的に戻値が正の値だと a > b、負の値だと a < b、０だと a == b を表すと考えれば良い（要するに a - b）。ただこれは昇順の場合であって、降順（逆順）にしたければ、大小を反転（b - a）すれば良いことになる。これも他の言語でも使えることが多いので、覚えておくと役に立つ。

　ついでにこれもソート第２キーを加えてみよう。この場合は比較クラス（関数）の MyComparer にだけ変更を加えれば良い。プロジェクト共有で使用している等なら、一度にすべてのソート方法を変更できるメリットもある。ラムダ式版と合わせて使い分けをすると良いだろう。

●比較クラス（関数）に第２キーを加える

//比較クラス（比較関数）
public class MyComparer<T> : IComparer<T[]> where T : IComparable
{
    public int Compare(T[] a, T[] b)  {
        if (a[2].CompareTo(b[2]) == 0)  //第１キーが同じなら
        {
            return a[1].CompareTo(b[1]);  //第２キー：昇順
        }
        return b[2].CompareTo(a[2]);  //第１キー：降順
    }
}

[[3, 2, 300],
[4, 0, 200],
[0, 1, 200],
[1, 3, 100],
[2, 4, 100]]

　内容的にはラムダ式版の第２キーを加えたものと同じものになる。Compare() 関数内は if 文で書いているが、ラムダ式のときのように三項演算子（条件演算子）で return しても良い。ただ if 文なら第３キーや特殊な条件を加えたくなったとき、非常に簡単に書ける利点がある。

　どちらの書き方が良いというわけでなく、保守性・拡張性を考えるか、一発簡潔に書くか等、用途によって使い分けるのが良いだろう。

■多次元配列でのソート (クイックソート)

　多次元配列でのソートは初めから用意されてはいないので、ここからは一般的なソートアルゴリズムを用いた方法になる。多次元配列は内部的にはひとつづきなので、要素ごとに交換しなくてはならないことに注意しよう。

　また、２次元配列の場合は縦方向（列をキーに行をソート）と横方向（行をキーに列をソート）の２つがあるが、とりあえずはジャグ配列版と比較のためにも縦方向のソートで書いてみよう。

●２次元配列（多次元配列）のクイックソート（縦方向）

using System;
using System.Collections.Generic;
using System.Text;

//２次元配列のクイックソート(縦方向)
public static void QuickSortRow<T>(T[,] arr, int sortIndex, int first, int last, IComparer<T> comp)
{
    int i = first;  //前方検索インデクス
    int j = last;   //後方検索インデクス
    T p = Median(arr[i, sortIndex], arr[(j - i) / 2 + i, sortIndex], arr[j, sortIndex], comp);
    int col = arr.GetLength(1);

    while (true)
    {
        while (comp.Compare(arr[i, sortIndex], p) < 0) {   //基準値以上の位置まで前方検索
            i++;
        }
        while (comp.Compare(arr[j, sortIndex], p) > 0) {   //基準値以下の位置まで後方検索
            j--;
        }
        if (i >= j) {    //交差したら終了
            break;
        }

        //スワップ
        for (int k = 0; k < col; k++) {
            T tmp = arr[i, k];
            arr[i, k] = arr[j, k];
            arr[j, k] = tmp;
        }

        i++;
        j--;
    }

    //基準値より２分割して再帰呼び出し(２分割できないときは再帰停止)
    if (first < i - 1) {
        QuickSortRow(arr, sortIndex, first, i - 1, comp);
    }
    if (j + 1 < last) {
        QuickSortRow(arr, sortIndex, j + 1, last, comp);
    }
}

//独自の Comparer（IComparer）用
public static void QuickSortRow<T>(T[,] arr, int sortIndex, IComparer<T> comp)
{
    QuickSortRow(arr, sortIndex, 0, arr.GetLength(0) - 1, comp);
}

//既定の Comparer（IComparer）用
public static void QuickSortRow<T>(T[,] arr, int sortIndex) where T : IComparable
{
    QuickSortRow(arr, sortIndex, 0, arr.GetLength(0) - 1, Comparer<T>.Default);
}

//x, y, z の中央値を返す
public static T Median<T>(T x, T y, T z, IComparer<T> comp)
{
    if (comp.Compare(x, y) < 0)
    {
        if (comp.Compare(y, z) < 0)      return y;
        else if (comp.Compare(z, x) < 0) return x;
        else                             return z;
    }
    else
    {
        if (comp.Compare(z, y) < 0)      return y;
        else if (comp.Compare(x, z) < 0) return x;
        else                             return z;
    }
}


public static void Main()
{
    //多次元配列
    int[,] grid = {
        {0, 1, 200},
        {1, 3, 100},
        {2, 4, 100},
        {3, 2, 300},
        {4, 0, 200},
    };

    QuickSortRow(grid, 1);
    Console.WriteLine(ToString(grid));  //デバッグ用関数（※下記を参照）
}

[[4, 0, 200],
[0, 1, 200],
[3, 2, 300],
[1, 3, 100],
[2, 4, 100]]

(※) ToString(T[,]) は前回作った関数を参照（配列の内容を文字列化→表示するだけのもの）

　クイックソートのアルゴリズムは、Wikipedia でも見て欲しい。コードも実装例を２次元配列用に改造したものである。実は以前に書いた Java 版（横方向）の焼き直しだったりもする。

　なお、基準値(p : Pivot) は簡略のために、検索範囲の最初と最後の値を加算して２で割る方法(平均値)でも良い。ここではジェネリック型で作っているので、Wikipedia に載っている med3 関数（中間値[中央値]）を使っている（ジェネリック型で演算はできないので）。このピボットの値をどう取るかで効率が変わるので色々研究されているらしい。実際には元の並びにもよるのでやりやすいものを使えば良いだろう。

　また注意点としては、このクイックソートは安定ソートではないので、同値の場合は、他の列の並びは不定になる。他の列の順序も考慮に入れたいのなら、安定ソートのものでソート関数内に第２ソートキー比較などを入れる工夫が必要になるだろう。挿入ソートを２回使う手もある。ユニーク値や連番なら問題はない。

　逆順(降順)にしたいなら、以下の Comparer を使えば良い。

●逆順（降順）の Comparer を定義して使う

//逆順（降順）
public class RevComparer<T> : IComparer<T> where T : IComparable
{
    public int Compare(T a, T b)  {
        return b.CompareTo(a);    //降順
    }
}

//メインでは...
QuickSortRow(grid, 1, new RevComparer<int>());

[[2, 4, 100],
[1, 3, 100],
[3, 2, 300],
[0, 1, 200],
[4, 0, 200]]

■多次元配列でのソート (挿入ソート)

　もう１つ、安定ソートを使いたいときのために、挿入ソートも書いておこう。といってもこれも以前 Java で書いた「２次元配列の挿入ソート(横方向)」の焼き直しである。縦と横の方向を入れ替えただけなので、難しくはないだろう。

●２次元配列（多次元配列）の挿入ソート（縦方向）

using System;
using System.Collections.Generic;
using System.Text;

//２次元配列の挿入ソート(縦方向)
public static void InsertionSortRow<T>(T[,] arr, int sortIndex, IComparer<T> comp)
{
    int row = arr.GetLength(0);
    int col = arr.GetLength(1);
    T[] tmp = new T[col];

    for (int i = 1; i < row; i++)
    {
        T t = arr[i, sortIndex];
        if (comp.Compare(arr[i - 1, sortIndex], t) > 0)
        {
            //列の退避
            for (int k = 0; k < col; k++)
            {
                tmp[k] = arr[i, k];
            }

            //上へずらす
            int j = i;
            do {
                for (int k = 0; k < col; k++)
                {
                    arr[j, k] = arr[j - 1, k];
                }
                j--;
            } while (j > 0 && comp.Compare(arr[j - 1, sortIndex], t) > 0);

            //列のストア
            for (int k = 0; k < col; k++)
            {
                arr[j, k] = tmp[k];
            }
        }
    }
}

//既定の Comparer（IComparer）用
public static void InsertionSortRow<T>(T[,] arr, int sortIndex) where T : IComparable
{
    InsertionSortRow(arr, sortIndex, Comparer<T>.Default);
}


public static void Main()
{
    //多次元配列
    int[,] grid = {
        {0, 1, 200},
        {1, 3, 100},
        {2, 4, 100},
        {3, 2, 300},
        {4, 0, 200},
    };

    InsertionSortRow(grid, 1);  //昇順
    //InsertionSortRow(grid, 1, new RevComparer<int>());  //降順
    Console.WriteLine(ToString(grid));  //デバッグ用関数（※下記を参照）
}

[[4, 0, 200],
[0, 1, 200],
[3, 2, 300],
[1, 3, 100],
[2, 4, 100]]

(※) ToString(T[,]) は前回作った関数を参照（配列の内容を文字列化→表示するだけのもの）

　逆順（降順）にしたい場合は、RevComparer を使う。安定ソートなので、２回以上のソート（別々のキー[列]で）しても、並びは保持されるので、第2, 3,…ソートキーを使うのと同じ効果になる（※ただし、効率は良くない）。

■多次元配列→ジャグ配列変換してソート

　これは、多次元配列では内部的にはひとつづきのため、要素ごとに処理する必要があるので、いっそのことジャグ配列に変換してしまおうという方法だ。

　「多次元配列→ジャグ配列変換」は以前に作ったものをそのまま使う。あとは「ジャグ配列でのソート」と同じだ。

●多次元配列→ジャグ配列変換（→前回作ったもの）してからソート

using System;
using System.Collections.Generic;
using System.Text;

/**
 * 多次元配列をジャグ配列に変換
 */
public static T[][] ToJaggedArray<T>(T[,] arr)
{
    int row = arr.GetLength(0);
    int col = arr.GetLength(1);

    T[][] jag = new T[row][];

    for (int i = 0; i < row; i++)
    {
        jag[i] = new T[col];
        for (int j = 0; j < col; j++)
        {
            jag[i][j] = arr[i, j];
        }
    }

    return jag;
}


public static void Main()
{
    //多次元配列
    int[,] grid = {
        {0, 1, 200},
        {1, 3, 100},
        {2, 4, 100},
        {3, 2, 300},
        {4, 0, 200},
    };

    int[][] jag = ToJaggedArray(grid);  //多次元配列→ジャグ配列 変換
    Array.Sort(jag, (a, b) => a[1] - b[1]);  //昇順(index=1)
    //Array.Sort(jag, (a, b) => b[1] - a[1]);  //降順(index=1)
    Console.WriteLine(ToString(jag));  //デバッグ用関数（※下記を参照）
}

[[2, 4, 100],
[1, 3, 100],
[3, 2, 300],
[0, 1, 200],
[4, 0, 200]]

(※) ToString(T[][]) は前回作った関数を参照（配列の内容を文字列化→表示するだけのもの）

　まぁ、はじめからジャグ配列を使うのが一番楽だが、負荷が許せるなら、変換するのもアリだろう。

■キーと値の２つの配列でのソート

　もう１つ、今回の２次元配列のテーマからは少し外れるのだが、C# には「ソート対象となる１次元配列と、その項目に対応する別の１次元配列」をソートできる Array.Sort(Array, Array) がオーバーロードされている。まるで連想配列をソートするような感じになる。

using System;
using System.Collections.Generic;

string[] name = {"Alice", "Becky", "Cindy", "Daisy", "Eliza"};
int[] value = {95, 85, 100, 72, 78};

Array.Sort(value, name);  //昇順
//Array.Sort(value, name, new RevComparer<int>());  //降順

for (int i = 0; i < name.Length; i++)
{
    Console.WriteLine(name[i] + " => " + value[i]);
}

Daisy => 72
Eliza => 78
Becky => 85
Alice => 95
Cindy => 100

　引数は Array.Sort(ソート対象の配列, 対応する配列, [IComparer]) となっている。

　ちなみに、コメントアウトされている「RevComparer」（逆順用 Comparer）で降順ソートすると結果は以下のようになる。

Cindy => 100
Alice => 95
Becky => 85
Eliza => 78
Daisy => 72

　ソートのキーとなる配列と値の配列（項目に対応する配列）は別々に作るので、型に自由が利くのが特徴だ。値の配列は何でも良いので、クラスや構造体の配列などをソートすることもできる。普段はクラスや構造体でデータを保持しておいて、ソートしたいときだけキーとなる配列を生成する等もできるだろう。

　Comparer（RevComparer）などもあらかじめ static で作っておけば（int など利用頻度が高い型を別に作っておけば）、毎回 new しなくて済むので実行速度がはやくなる。色々工夫してみると良いだろう。