FC2ブログ
ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »アルゴリズム実証実験
このページの記事一覧

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


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


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


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

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

●Comparator を用いた2次元配列のソート(一番単純な例)
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] をキーにソート(降順)
}
});
}

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

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

●Comparator を用いた2次元配列のソート(第2ソートキーを加える)
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]; //第2ソートキー [1] でソート(降順)
} else {
return o1[0] - o2[0]; //第1ソートキー [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 を用いた2次元配列のソート(比較用クラスを作る)
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 を用いた2次元配列のソートを降順(逆順)にする(比較関数のみ)
・・・(略)・・・
//比較関数
@Override
public int compare(int[] o1, int[] o2) {
return o2[sortIndex] - o1[sortIndex]; //a>b(>c>d...) としたいとき
}
・・・(略)・・・


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

●Comparator を用いた2次元配列のソートにソートオーダー(昇順/降順)を加える
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...) としたいとき
}
}
}


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

●Comparator を用いた2次元配列のソートに第2ソートキーを加える
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; //第2ソートキー
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;

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

/** 昇順フラグ(第2キー) (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]) { //第1キーが等しいときは、第2キーで比較
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...) としたいとき
}
}
}
}

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

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


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

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

●2次元配列のクイックソート(横方向)
/**<h1>2次元配列のクイックソート(範囲指定)</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--;
}

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

/**<h1>2次元配列のクイックソート</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) は簡略のため検索範囲の最初と最後の値を加算して2で割っているが(平均値)、Wikipedia の med3 関数のような中間値(中央値)でも良い。このピボットの値をどう取るかで効率が変わるので色々研究されているらしい。実際には元の並びにもよるのでやりやすいものを使えば良いだろう。

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

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

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

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

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

●今回の実行速度の結果
要素数実行速度
10クイックソート>マージソート>挿入ソート
50クイックソート>挿入ソート>マージソート
100クイックソート>マージソート>挿入ソート
1000クイックソート>マージソート>挿入ソート
10000クイックソート>マージソート>挿入ソート
50000クイックソート>マージソート>挿入ソート
※速い>遅い

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

(参考) 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>2次元配列のマージソート</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;
}

//配列を2分割
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]; //2分割のため、半端は必ず最後の1つになる
}
}

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

/**<h1>2次元配列のマージ(マージソート用)</h1>
* <p>col 方向でのソート。長さの違う配列は基本的に不可。昇順にマージされる。再帰用。</p>
* @param dst : マージされた結果配列
* @param sortIndex : ソートキーとなる row インデクス (arr[row][col])
* @param arr1 : マージする配列1
* @param arr2 : マージする配列2
*/
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>2次元配列の挿入ソート</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>2次元配列のクイックソート(範囲指定)</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--;
}

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

/**<h1>2次元配列のクイックソート</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>2次元配列のマージソート</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;
}

//配列を2分割
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]; //2分割のため、半端は必ず最後の1つになる
}
}

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

/**<h1>2次元配列のマージ(マージソート用)</h1>
* <p>col 方向でのソート。長さの違う配列は基本的に不可。昇順にマージされる。再帰用。</p>
* @param dst : マージされた結果配列
* @param sortIndex : ソートキーとなる row インデクス (arr[row][col])
* @param arr1 : マージする配列1
* @param arr2 : マージする配列2
* @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)); //降順

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

 他のアルゴリズムでも色々やってみると良いだろう。


(関連記事)
【Java】連想配列(Map)を値でソートする
【Java】配列要素の反転(reverse)
【Java】配列, リスト(List), 連想配列(Map) の初期化


■参考にできる書籍


関連記事
スポンサーサイト



category: Java

thread: プログラミング

janre: コンピュータ

tag: 配列操作  ソート  アルゴリズム実証実験 
tb: 0   cm: --


プロフィール

Social

検索フォーム

全記事一覧

ユーザータグ

最新記事

リンク

カテゴリ

PR

PR

▲ Pagetop