ソート - ヽ｜∵｜ゝ(Fantom) の開発blog？

このページの記事一覧

2016/12/07 【C#】連想配列(Dictionary)を値 or キーでソート
2016/12/05 【C#】２次元配列（ジャグ配列・多次元配列）のソート
2015/04/19 【Java】連想配列(Map)を値でソートする
2015/04/08 【Java】２次元配列のソート

« prev next »

【C#】連想配列(Dictionary)を値 or キーでソート

2016/12/07 Wed [edit]

　このテーマはググればいくらでも出てくるので、どちらかというと自分用メモ。先に述べてしまうと、初めの LINQ 的な書き方が一番簡単だろう。ただ、他の方法もあったので、それも少しまとめてみた感じ。色々な書き方を知っておくと、他言語に移植するとき等にも役に立つからだ。

■IEnumerableでのソート (LINQ)
■KeyValuePair の List でのソート (ラムダ式)
■KeyValuePair の List でのソート (delegate)
■KeyValuePair の List でのソート (IComparer)
■キーと値の２つの配列でのソート

■IEnumerable でのソート (LINQ)

　LINQ (System.Linq) が使えるなら、とりあえずこれを使うのが一番楽だろう。内容的には Enumerable(IEnumerable) を使うことになる。キーでのソートも、値でのソートもプロパティを変えるだけで同様にできる。

●値でのソート (IEnumerable)

using System;
using System.Collections.Generic;
using System.Linq;

Dictionary<string, int> dic = new Dictionary<string, int>() {
    { "Becky", 85 },
    { "Daisy", 72 },
    { "Alice", 95 },
    { "Eliza", 78 },
    { "Cindy", 100 },
};

var sorted = dic.OrderBy((x) => x.Value);  //昇順
//var sorted = dic.OrderByDescending((x) => x.Value);  //降順

foreach (var v in sorted)
{
    Console.WriteLine(v.Key + " => " + v.Value);
}

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

　コメントアウトの方は降順になる。キーでのソートはソート対象を変えるだけで良い（x.Value → x.Key に変更）。

●キーでのソート (IEnumerable)

var sorted = dic.OrderBy((x) => x.Key);  //昇順
//var sorted = dic.OrderByDescending((x) => x.Key);  //降順

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

■KeyValuePair の List でのソート (ラムダ式)

　これはキーと値のペア（KeyValuePair）のリストを作って、それをソートする方法だ。他の言語でもよく使われる方法なので、覚えておくと役に立つ。List.Sort() はラムダ式が使えるようなので、簡潔に書くことも可能だ。

●値でのソート (KeyValuePair の List とラムダ式)

using System;
using System.Collections.Generic;

Dictionary<string, int> dic = new Dictionary<string, int>() {
    { "Becky", 85 },
    { "Daisy", 72 },
    { "Alice", 95 },
    { "Eliza", 78 },
    { "Cindy", 100 },
};

List<KeyValuePair<string, int>> list = new List<KeyValuePair<string, int>>(dic);
list.Sort((a, b) => a.Value - b.Value);  //昇順
//list.Sort((a, b) => b.Value - a.Value);  //降順

foreach (var v in list)
{
    Console.WriteLine(v.Key + " => " + v.Value);
}

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

　コメントアウトの方は降順になる。キーでのソートはソート対象を変えるだけで良い（x.Value → x.Key に変更）。なお、比較には CompareTo() を使っている。

●キーでのソート (KeyValuePair の List とラムダ式)

list.Sort((a, b) => a.Key.CompareTo(b.Key));  //昇順
//list.Sort((a, b) => b.Key.CompareTo(a.Key));  //降順

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

■KeyValuePair の List でのソート (delegate)

　これは上記のラムダ式版の別表記と言っても良いのだが、改めて delegate を使えると覚えておくと、例えば、リアルタイムにソート方法を変更するような実装もできると考えることができる。まぁ、引き出しは多いことに越したことはない。

●値でのソート (KeyValuePair の List と delegate)

using System;
using System.Collections.Generic;

Dictionary<string, int> dic = new Dictionary<string, int>() {
    { "Becky", 85 },
    { "Daisy", 72 },
    { "Alice", 95 },
    { "Eliza", 78 },
    { "Cindy", 100 },
};

List<KeyValuePair<string, int>> list = new List<KeyValuePair<string, int>>(dic);
list.Sort(delegate(KeyValuePair<string, int> a, KeyValuePair<string, int> b) {
    return a.Value - b.Value;  //昇順
    //return b.Value - a.Value;  //降順
});

foreach (var v in list)
{
    Console.WriteLine(v.Key + " => " + v.Value);
}

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

　コメントアウトの方は降順になる。キーでのソートはソート対象を変えるだけで良い（x.Value → x.Key に変更）。なお、比較には CompareTo() を使っている。

●キーでのソート (KeyValuePair の List と delegate)

list.Sort(delegate(KeyValuePair<string, int> a, KeyValuePair<string, int> b) {
    return a.Key.CompareTo(b.Key);  //昇順
    //return b.Key.CompareTo(a.Key);  //降順
});

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

■KeyValuePair の List でのソート (IComparer)

　ICompare(Comparer) も使えるのでやってみよう。このような比較関数（クラス）は他の言語でもよくあるので、移植もしやすい。ちなみに以前書いた Java での連想配列(Map)でのソートと全く同じ構成となる。

●値(or キー)でのソート (KeyValuePair の List と IComparer)

using System;
using System.Collections.Generic;

public static void Main()
{
    Dictionary<string, int> dic = new Dictionary<string, int>() {
        { "Becky", 85 },
        { "Daisy", 72 },
        { "Alice", 95 },
        { "Eliza", 78 },
        { "Cindy", 100 },
    };

    List<KeyValuePair<string, int>> list = new List<KeyValuePair<string, int>>(dic);
    list.Sort(new MyComparer<string, int>());

    foreach (var v in list)
    {
        Console.WriteLine(v.Key + " => " + v.Value);
    }
}

//比較クラス(関数)
public class MyComparer<K,V> : IComparer<KeyValuePair<K,V>>
    where K : IComparable
    where V : IComparable
{
    public int Compare(KeyValuePair<K,V> a, KeyValuePair<K,V> b)  {
        return a.Value.CompareTo(b.Value);  //値 昇順
        //return b.Value.CompareTo(a.Value);  //値 降順
        //return a.Key.CompareTo(b.Key);  //キー 昇順
        //return b.Key.CompareTo(a.Key);  //キー 降順
    }
}

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

　上記の例では１つのクラスでまとめてしまったため、型パラメーターの制約を複数書いてしまっているが、値のみ(V)・キーのみ(K)とわかっているなら、制約はどちらかだけでも良い。同じようなことは delegate 版でもできると思うが、１つのクラスにまとめた利点としては、プロパティなどを追加して、いつでもソート方法を変更できる・同じソート方法を共有できること等にある。用途に合わせて使い分けるのも良いだろう。

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

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

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

using System;
using System.Collections.Generic;

public static void Main()
{
    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 < value.Length; i++)
    {
        Console.WriteLine(name[i] + " => " + value[i]);
    }
}

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

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 しなくて済むので実行速度がはやくなる。色々工夫してみると良いだろう。

関連記事

【C#】最大公約数を求める/分数の約分をする（ユークリッドの互除法）
【C#】文字列 → float (浮動小数点) 変換でエラーが出るときは…
【C#】倍数での Floor, Ceil, Round（一定間隔での切り捨て、切り上げ、四捨五入） [double 版]
【C#】MD5, SHA1, SHA256, SHA384, SHA512 等のハッシュ値を生成する
【C#】連想配列(Dictionary)を値 or キーでソート

スポンサーサイト

category: C#

thread: プログラミング

janre: コンピュータ

tag: C# 連想配列配列操作ソート

tb: 0 cm: --

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

2016/12/05 Mon [edit]

　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

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

関連記事

category: C#

thread: プログラミング

janre: コンピュータ

tag: C# 配列操作ソート

tb: 0 cm: --

【Java】連想配列(Map)を値でソートする

2015/04/19 Sun [edit]

　キーでのソート(昇順)は TreeMap を使えば勝手にやってくれる。しかし集計など、値でのソートをしたいことも多い。その場合はリストなどを中継し、Comparator で並び変えると良い。

●連想配列(Map)を値でソート(昇順/降順)

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

//初期化
Map<String, Integer> map = new HashMap<String, Integer>(){    //TreeMap でも良い
    {
        put("Alice", 13);
        put("Becky", 10);
        put("Candy",  6);
        put("Daisy", 99);
        put("Eliza",  9);
    }
};

//Map.Entry のリストを作る
List<Entry<String, Integer>> entries = new ArrayList<Entry<String, Integer>>(map.entrySet());

//Comparator で Map.Entry の値を比較
Collections.sort(entries, new Comparator<Entry<String, Integer>>() {
    //比較関数
    @Override
    public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
        return o1.getValue().compareTo(o2.getValue());    //昇順
        //return o2.getValue().compareTo(o1.getValue());    //降順
    }
});

//確認用
for (Entry<String, Integer> e : entries) {
    System.out.println(e.getKey() + " = " + e.getValue());
}

//Java 8 なら...
//entries.forEach(e -> System.out.println(e.getKey() + " = " + e.getValue()));

　構造としてはキーと値のペア(Map.Entry)のリストを作り、そのリストをソートしている感じ。要素はオブジェクトの参照なので、キーでも値でも取り出せる。この例では Comparator を匿名クラスで作ってるが、「２次元配列のソート」のときのように、独立したクラスとして定義して置いて、フラグで昇順・降順を切り替えるのも良いだろう。

　キーを逆順(降順)ソートしたい場合は、同じような考え方でできる。

●連想配列(Map)をキーで降順ソート

//キーのリストを作る
List<String> keylist = new ArrayList<String>(map.keySet());

//Comparator でキーを降順ソート
Collections.sort(keylist, new Comparator<String>() {
    //比較関数
    @Override
    public int compare(String o1, String o2) {
        return o2.compareTo(o1);
    }
});

//確認用
for (String key : keylist) {
    System.out.println(key + " = " + map.get(key));
}

//Java 8 なら...
//keylist.forEach(e -> System.out.println(e + " = " + map.get(e)));

　昇順なら Collections.sort(keylist) だけで良いね（TreeMap なら必要ない）。いずれにしても連想配列は順番(連番)という概念はあまりないので、List などを間に挟むと、色々操作しやすい。

関連記事

category: Java

thread: プログラミング

janre: コンピュータ

tag: 連想配列配列操作ソート

tb: 0 cm: --

【Java】２次元配列のソート

2015/04/08 Wed [edit]

　２次元配列でのソートを調べていたところ、基本的に Comparator でのやり方が多かったのと、Comparator の例だと縦方向（array[y][x] の場合）でのソートが中心なので、横方向でのソートを一般的なソートアルゴリズムでやってみようと思った。

(※) ソートの結果は Comparator の作り方による

■Comparator を用いた２次元配列のソート(縦方向)
■２次元配列のクイックソート(横方向)
■２次元配列のマージソート(横方向)
■２次元配列の挿入ソート(横方向)
■横(列)方向の逆順(降順)ソート

■Comparator を用いた２次元配列のソート(縦方向)

　はじめに、Comparator を用いた、縦方向の２次元ソートを書いておこう。こっちの方が汎用性は高いので、使い方を覚えれば、柔軟なソートができて便利だ。ソート自体は「Arrays.sort()」を使う。

●Comparator を用いた２次元配列のソート（一番単純な例）

import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
    int[][] arr = {
        {5, 2},
        {1, 4},
        {3, 5},
        {4, 3},
        {2, 1}
    };

    Arrays.sort(arr, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0] - o2[0];    //[0] をキーにソート(昇順)
            //return o2[0] - o1[0];    //[0] をキーにソート(降順)
        }
    });
}

　結果は一番上の画像(右側)のようになる。

　この例では同じ値はないが、ソートするキーが同じ値の場合、比較関数を少しいじれば、第２ソートキーを付け加えることもできる。

●Comparator を用いた２次元配列のソート（第２ソートキーを加える）

import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
    int[][] arr = {
        {5, 2},
        {1, 4},
        {3, 5},
        {4, 3},
        {2, 1}
    };

    Arrays.sort(arr, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            if (o1[0] == o2[0]) {
                return o2[1] - o1[1];    //第２ソートキー [1] でソート(降順)
            } else {
                return o1[0] - o2[0];    //第１ソートキー [0] でソート(昇順)
            }
        }
    });
}

　ポイントは、Comparator インターフェイスの「compare()」メソッドを Override しなくてはならないわけだが、この関数の戻値が「負の値」のとき、配列の要素は昇順になり、「正の値」のときは降順になるという点だ（要するに a < b のとき、a - b = 負の値、a > b のとき、a - b = 正の値、a == b のとき、a - b = 0 として並びを決めていると考えれば良い）。今回は int 型なので、引き算をしているが、他のオブジェクト（Integer、String 等）でも比較できるものはだいたい「Comparable インターフェイス」を持っているので、そのオブジェクトの「compareTo()」の戻値をそのまま返せば良い。

　毎回同じようなソートをするなら、Comparator を implements した比較用クラスを作ってしまえば、使い回しも可能だ。

●Comparator を用いた２次元配列のソート（比較用クラスを作る）

import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
    int[][] arr = {
        {5, 2},
        {1, 4},
        {3, 5},
        {4, 3},
        {2, 1}
    };

    MyComparator comparator = new MyComparator(0);
    Arrays.sort(arr, comparator);
}

//比較用クラス(内部クラスにするなら static にすれば良い)
public class MyComparator implements Comparator<int[]> {

    /** ソートキーとなる col インデクス (arr[row][col]) */
    public int sortIndex = 0;

    //コンストラクタ
    public MyComparator(int sortIndex) {
        this.sortIndex = sortIndex;
    }

    //比較関数
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1[sortIndex] - o2[sortIndex];    //a<b(<c<d...) としたいとき
    }
}

　「sortIndex」は面倒なので public スコープにしてあるが、private スコープにして setter を作るのも良いだろう。

　降順（逆順）にするには、上記の比較関数（compare()）の戻値を逆にする。

●Comparator を用いた２次元配列のソートを降順(逆順)にする（比較関数のみ）

・・・(略)・・・
    //比較関数
    @Override
    public int compare(int[] o1, int[] o2) {
        return o2[sortIndex] - o1[sortIndex];    //a>b(>c>d...) としたいとき
    }
・・・(略)・・・

　また毎回書き直すのが面倒だと思ったら、とりわけ int 型などは使用頻度は高いので、メンバを付け加えた独立したクラスとして作って置くのが良い。その方が機能を追加しやすい。例えば、ソートオーダー（昇順/降順）を自由に切り替えられるようにするには、以下のようにする。

●Comparator を用いた２次元配列のソートにソートオーダー（昇順/降順）を加える

import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
・・・(略)・・・
    MyComparator comparator = new MyComparator(0, false);  //降順になる
    Arrays.sort(arr, comparator);
}

//比較用クラス(内部クラスにするなら static にすれば良い)
public class MyComparator implements Comparator<int[]> {

    /** ソートキーとなる col インデクス (arr[row][col]) */
    public int sortIndex = 0;

    /** 昇順フラグ (true = 昇順 / false = 降順) */
    public boolean ascend = true;

    //コンストラクタ
    public MyComparator(int sortIndex) {
        this.sortIndex = sortIndex;
    }
    public MyComparator(int sortIndex, boolean ascend) {
        this.sortIndex = sortIndex;
        this.ascend = ascend;
    }

    //比較関数
    @Override
    public int compare(int[] o1, int[] o2) {
        if (ascend) {
            return o1[sortIndex] - o2[sortIndex];    //a<b(<c<d...) としたいとき
        } else {
            return o2[sortIndex] - o1[sortIndex];    //a>b(>c>d...) としたいとき
        }
    }
}

　またこのように考えれば、同値のときの第２ソートキーを付け加えるのも簡単だ。同じようにメンバを追加して、比較関数の条件を加えれば良い。

●Comparator を用いた２次元配列のソートに第２ソートキーを加える

import java.util.Arrays;
import java.util.Comparator;

//メイン
public static void main(String[] args) throws Exception {
・・・(略)・・・
    MyComparator comparator = new MyComparator(1, false);  //降順になる
    comparator.sortIndex2 = 0;    //第２ソートキー
    comparator.ascend2 = false;    //降順になる
    Arrays.sort(arr, comparator);
}

//比較用クラス(内部クラスにするなら static にすれば良い)
public class MyComparator implements Comparator<int[]> {

    /** ソートキーとなる col インデクス (arr[row][col]) */
    public int sortIndex = 0;

    /** 昇順フラグ (true = 昇順 / false = 降順) */
    public boolean ascend = true;

    /** ソートキー(第２キー)となる col インデクス (arr[row][col]) */
    public int sortIndex2 = 1;

    /** 昇順フラグ(第２キー) (true = 昇順 / false = 降順) */
    public boolean ascend2 = true;

    //コンストラクタ
    public MyComparator(int sortIndex) {
        this.sortIndex = sortIndex;
    }
    public MyComparator(int sortIndex, boolean ascend) {
        this.sortIndex = sortIndex;
        this.ascend = ascend;
    }

    //比較関数
    @Override
    public int compare(int[] o1, int[] o2) {
        if (o1[sortIndex] == o2[sortIndex]) {    //第１キーが等しいときは、第２キーで比較
            if (ascend2) {
                return o1[sortIndex2] - o2[sortIndex2];    //a<b(<c<d...) としたいとき
            } else {
                return o2[sortIndex2] - o1[sortIndex2];    //a>b(>c>d...) としたいとき
            }
        } else {
            if (ascend) {
                return o1[sortIndex] - o2[sortIndex];    //a<b(<c<d...) としたいとき
            } else {
                return o2[sortIndex] - o1[sortIndex];    //a>b(>c>d...) としたいとき
            }
        }
    }
}

　今回は割愛したが、第２ソートキーを加えたコンストラクタを付け加えるのも良いだろう。

　この手のインターフェイスや関数は他の言語にもあるので（Ｃ系やVB等の IComparer など）、考え方がわかれば、色々応用は効く。

－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　
■一般的なソートアルゴリズムを用いた２次元配列のソート(横方向)

　次に、横方向でのソートを一般的なソートアルゴリズムでやってみる。これは Arrays.sort() ではできないので、自作することになる。

●2次元配列のクイックソート(横方向)

/**<h1>２次元配列のクイックソート(範囲指定)</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。主に再帰用。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 * @param first ： 範囲の開始インデクス
 * @param last ： 範囲の終了インデクス
 */
public static final void qsort(int[][] arr, final int sortIndex, final int first, final int last) {
    int i, j, k, p, tmp;

    i = first;    //前方検索インデクス
    j = last;    //後方検索インデクス
    p = (arr[sortIndex][i] + arr[sortIndex][j]) / 2;    //基準値(※オーバフロー注意)

    final int row = arr.length;

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

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

        i++;
        j--;
    }

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

/**<h1>２次元配列のクイックソート</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。範囲は最初から最後まで。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 */
public static final void qsort(int[][] arr, final int sortIndex) {
    qsort(arr, sortIndex, 0, arr[0].length - 1);
}

→ 逆順(降順)でのクイックソート

　クイックソートのアルゴリズムは検索すればいくらでも出てくるので割愛。なお、基準値(p : Pivot) は簡略のため検索範囲の最初と最後の値を加算して２で割っているが(平均値)、Wikipedia の med3 関数のような中間値(中央値)でも良い。このピボットの値をどう取るかで効率が変わるので色々研究されているらしい。実際には元の並びにもよるのでやりやすいものを使えば良いだろう。

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

　逆順(降順)にしたいなら、後述する Comparator を用いる方法がある。昇順/降順の切り替えのみなら、boolean 型のフラグを引数にして、比較を逆にしても良いだろう。

　それと仕様として、各行の長さが違う配列には対応してない。特に例外処理は設けてないので、必要なら「ArrayIndexOutOfBoundsException」を catch か throws するようにした方が良いだろう。

　また、開始インデクスと終了インデクスの引数を持っている方の「qsort(int[][],int,int,int)」は主に再帰用なので、直接使うことがないなら、private スコープにしても良いだろう。引数の少ない「qsort(int[][],int)」の方は初めから最後までのインデクスで、引数の多い方をオーバーロードしてる感じになっている。

　あと、これを作っているとき、２次元ということもあり、アルゴリズムによる実行速度も気になったので、他のアルゴリズムとの比較もしてみた。とはいえ、測定してみたら、今回作ったものではクイックソートが一番速かったので、とりあえず qsort を使っていれば事足りるかもしれない。結果は環境や言語仕様などにも違いはあるみたいだね。アルゴリズムはあまり工夫してないし(ただスワップを列にしただけ)、スマホや携帯の場合、再帰構造はメモリを喰うので、要素数によっても変わるだろう。だからこの辺りはあくまでも適当な目安として考えて欲しい。

●今回の実行速度の結果

要素数	実行速度
10	クイックソート＞マージソート＞挿入ソート
50	クイックソート＞挿入ソート＞マージソート
100	クイックソート＞マージソート＞挿入ソート
1000	クイックソート＞マージソート＞挿入ソート
10000	クイックソート＞マージソート＞挿入ソート
50000	クイックソート＞マージソート＞挿入ソート

※速い＞遅い

　特に挿入ソートは 50～100 くらいだとむしろ速かったが、このアルゴリズムは要素数によってかなり遅くなるので、10000以上は使わない方がいいだろう。ちなみに以下の参考はＣ＋＋での比較。

(参考) 50以下挿入ソート、5万以下マージソート、あとはクイックソート
(参考) ソート(Wikipedia)

　ちなみに、Wikipedia の「ソートアルゴリズムの一覧」の「O(n²)」のような記号は「オーダー記法(ランダウの記号)」と言って、計算時間のおおよその目安を計るのに使われる。とりあえずよく使われるものとして、

　O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²)

※O(n) ・・・データ量が 2倍, 3倍,... のとき、計算時間が 2倍, 3倍,... になる。
※O(n²) ・・・データ量が 2倍, 3倍,... のとき、計算時間が 4倍(2²), 9倍(3²),... になる。
※計算量小[=速い] ＜計算量大[=遅い]

の順に計算時間がかかると覚えて置けば良いだろう。

●2次元配列のマージソート(横方向)

/**<h1>２次元配列のマージソート</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。再帰分割と結合。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 */
public static final void msort(int[][] arr, final int sortIndex) {
    final int col = arr[0].length;
    if (col <= 1) {        //分割できなくなったら、再帰停止
        return;
    }

    //配列を２分割
    final int row = arr.length;
    final int m = col / 2;    //半分より左(半端は切捨て：5 / 2 = 2)
    final int n = col - m;    //半分より右(半端はこっち：5 - 2 = 3)
    int[][] arr1 = new int[row][m];
    int[][] arr2 = new int[row][n];
    int i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < row; j++) {
            arr1[j][i] = arr[j][i];
            arr2[j][i] = arr[j][i + m];
        }
    }
    if (n > m) {
        for (j = 0; j < row; j++) {
            arr2[j][n - 1] = arr[j][col - 1];    //２分割のため、半端は必ず最後の１つになる
        }
    }

    //再帰分割と結合
    msort(arr1, sortIndex);    //再帰呼び出し(左半分の配列)
    msort(arr2, sortIndex);    //再帰呼び出し(右半分の配列)
    merge(arr, sortIndex, arr1, arr2);    //配列のマージ
}

/**<h1>２次元配列のマージ（マージソート用）</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。昇順にマージされる。再帰用。</p>
 * @param dst ： マージされた結果配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 * @param arr1 ： マージする配列１
 * @param arr2 ： マージする配列２
 */
private static final void merge(int[][] dst, final int sortIndex, final int[][] arr1, final int[][] arr2) {
    final int col1 = arr1[0].length;
    final int col2 = arr2[0].length;
    final int row = arr1.length;    //通常、arr1 と arr2 の row は同じ
    int i = 0;    //arr1 用インデクス
    int j = 0;    //arr2 用インデクス
    int p = 0;    //dst 用インデクス

    //小さい方を dst に追加
    int k;
    while (i < col1 && j < col2) {
        if (arr1[sortIndex][i] <= arr2[sortIndex][j]) {
            for (k = 0; k < row; k++) {
                dst[k][p] = arr1[k][i];
            }
            i++;
            p++;
        } else {
            for (k = 0; k < row; k++) {
                dst[k][p] = arr2[k][j];
            }
            j++;
            p++;
        }
    }
    
    //まだ残ってれば dst に追加
    while (i < col1) {
        for (k = 0; k < row; k++) {
            dst[k][p] = arr1[k][i];
        }
        i++;
        p++;
    }
    while (j < col2) {
        for (k = 0; k < row; k++) {
            dst[k][p] = arr2[k][j];
        }
        j++;
        p++;
    }
}

(参考) マージソート

→ 逆順(降順)でのマージソート

●2次元配列の挿入ソート(横方向)

/**<h1>２次元配列の挿入ソート</h1>
 * <p>col 方向のソート。長さの違う配列は基本的に不可。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 */
public static final void isort(int[][] arr, final int sortIndex) {
    final int row = arr.length;
    final int col = arr[0].length;
    final int[] tmp = new int[row];
    int i, j, k, t;
    for (i = 1; i < col; i++) {
        t = arr[sortIndex][i];
        if (arr[sortIndex][i - 1] > t) {
            //列の退避
            for (k = 0; k < row; k++) {
                tmp[k] = arr[k][i];
            }

            //比較
            j = i;
            do {
                for (k = 0; k < row; k++) {
                    arr[k][j] = arr[k][j - 1];    //右へずらす
                }
                j--;
            } while (j > 0 && arr[sortIndex][j - 1] > t);

            //退避した列のストア
            for (k = 0; k < row; k++) {
                arr[k][j] = tmp[k];
            }
        }
    }
}

(参考) 挿入ソート

　まぁ、ほぼまんまなので（無理矢理に列を追加したというか(笑)）、改良できそうならやった方が良いかもしれない。

－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　－　
■Comparator を用いて横(列)方向の逆順(降順)ソートをしてみる

　例えば、前述のクイックソートとマージソートを逆順(降順)にしてみる。上記の MyComparator と同じ作り方で、int 型に互換性のある Integer 型で Comparator を作ってみよう。Integer(int) 型はよく使うので、独立したクラスとして作って置くのも良い。

●Integer(int) 型の比較クラス

import java.util.Comparator;

/** Integer(int) 型での比較クラス */
public class IntegerComparator implements Comparator<Integer> {

    /** 昇順フラグ (true = 昇順 / false = 降順) */
    public boolean ascend = true;

    /**<h1>デフォルトコンストラクタ</h1>
     * <p>昇順リスト用。</p>
     */
    public IntegerComparator() {
    }

    /**<h1>並び方向の指定のコンストラクタ</h1>
     * <p>比較関数を昇順または降順にする。</p>
     * @param ascend ： true = 昇順 / false = 降順
     */
    public IntegerComparator(final boolean ascend) {
        this.ascend = ascend;
    }

    //比較関数
    @Override
    public int compare(Integer o1, Integer o2) {
        if (ascend) {
            return o1.compareTo(o2);    //昇順
        } else {
            return o2.compareTo(o1);    //降順
        }
    }
}

●逆順(降順)でのクイックソート (qsort に Comparator<Integer> を加えたもの)

/**<h1>２次元配列のクイックソート(範囲指定)</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。主に再帰用。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 * @param first ： 範囲の開始インデクス
 * @param last ： 範囲の終了インデクス
 * @param comparator ： Comparator<Integer>
 */
public static final void qsort(int[][] arr, final int sortIndex, final int first, final int last, 
    final Comparator<Integer> comparator) {
    int i, j, k, p, tmp;

    i = first;    //前方検索インデクス
    j = last;    //後方検索インデクス
    p = (arr[sortIndex][i] + arr[sortIndex][j]) / 2;    //基準値(※オーバフロー注意)

    final int row = arr.length;

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

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

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

/**<h1>２次元配列のクイックソート</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。範囲は最初から最後まで。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 * @param comparator ： Comparator<Integer>
 */
public static final void qsort(int[][] arr, final int sortIndex, final Comparator<Integer> comparator) {
    qsort(arr, sortIndex, 0, arr[0].length - 1, comparator);
}

→ 基本的なクイックソート

●逆順(降順)でのマージソート (msort に Comparator<Integer> を加えたもの)

/**<h1>２次元配列のマージソート</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。再帰分割と結合。</p>
 * @param arr ： 対象配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 * @param comparator ： Comparator<Integer>
 */
public static final void msort(int[][] arr, final int sortIndex, final Comparator<Integer> comparator) {
    final int col = arr[0].length;
    if (col <= 1) {        //分割できなくなったら、再帰停止
        return;
    }

    //配列を２分割
    final int row = arr.length;
    final int m = col / 2;    //半分より左(半端は切捨て：5 / 2 = 2)
    final int n = col - m;    //半分より右(半端はこっち：5 - 2 = 3)
    int[][] arr1 = new int[row][m];
    int[][] arr2 = new int[row][n];
    int i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < row; j++) {
            arr1[j][i] = arr[j][i];
            arr2[j][i] = arr[j][i + m];
        }
    }
    if (n > m) {
        for (j = 0; j < row; j++) {
            arr2[j][n - 1] = arr[j][col - 1];    //２分割のため、半端は必ず最後の１つになる
        }
    }
    
    //再帰分割と結合
    msort(arr1, sortIndex, comparator);    //再帰呼び出し(左半分の配列)
    msort(arr2, sortIndex, comparator);    //再帰呼び出し(右半分の配列)
    merge(arr, sortIndex, arr1, arr2, comparator);    //配列のマージ
}

/**<h1>２次元配列のマージ（マージソート用）</h1>
 * <p>col 方向でのソート。長さの違う配列は基本的に不可。昇順にマージされる。再帰用。</p>
 * @param dst ： マージされた結果配列
 * @param sortIndex ： ソートキーとなる row インデクス (arr[row][col])
 * @param arr1 ： マージする配列１
 * @param arr2 ： マージする配列２
 * @param comparator ： Comparator<Integer>
 */
private static final void merge(int[][] dst, final int sortIndex, final int[][] arr1, final int[][] arr2, 
    final Comparator<Integer> comparator) {
    final int col1 = arr1[0].length;
    final int col2 = arr2[0].length;
    final int row = arr1.length;    //通常、arr1 と arr2 の row は同じ
    int i = 0;    //arr1 用インデクス
    int j = 0;    //arr2 用インデクス
    int p = 0;    //dst 用インデクス

    //小さい方を dst に追加
    int k;
    while (i < col1 && j < col2) {
        if (comparator.compare(arr1[sortIndex][i], arr2[sortIndex][j]) <= 0) {
            for (k = 0; k < row; k++) {
                dst[k][p] = arr1[k][i];
            }
            i++;
            p++;
        } else {
            for (k = 0; k < row; k++) {
                dst[k][p] = arr2[k][j];
            }
            j++;
            p++;
        }
    }
    
    //まだ残ってれば dst に追加
    while (i < col1) {
        for (k = 0; k < row; k++) {
            dst[k][p] = arr1[k][i];
        }
        i++;
        p++;
    }
    while (j < col2) {
        for (k = 0; k < row; k++) {
            dst[k][p] = arr2[k][j];
        }
        j++;
        p++;
    }
}

→ 基本的なマージソート

　内容的には、比較部分を Comparator.compare() に置き換え、再帰呼び出しの引数にも加えただけである。

　メインは、

int[][] arr = {
    {5, 1, 3, 4, 2},
    {2, 4, 5, 3, 1}
};
qsort(arr, 0, new IntegerComparator(false));    //降順
//msort(arr, 0, new IntegerComparator(false));    //降順

のような感じで良い。結果は以下の様になる。