【Java入門】配列を高速にソートする方法

Javaで配列を高速にソートする方法について記載します。

配列を高速にソートする方法

Arraysクラスの、parallelSort メソッドを使用します。

構文

parallelSort( ソート対象の配列変数 )

※ 引数にはintやdoubleなどのプリミティブ型の配列やString型の配列も指定可能です。

戻り値

なし

まずは、Arrays.sort メソッドを使用してソートにかかる時間を計測します。

実行例（ Arrays.sort：１億の要素を持つ配列を昇順にソート）

// ランダムな値（0 < 10000）をもつ、int型の配列（要素は100000000）を生成
int[] intArray = new Random().ints(100000000, 0, 10000).toArray();

Arrays.sort( intArray ); // ソート

// 1回目：6.485秒
// 2回目：6.416秒
// 3回目：6.081秒

// ランダムな値（0 < 10000）をもつ、int型の配列（要素は100000000）を生成

int[] intArray = new Random().ints(100000000, 0, 10000).toArray();

Arrays.sort( intArray ); // ソート

// 1回目：6.485秒

// 2回目：6.416秒

// 3回目：6.081秒

次に、Arrays.parallelSort メソッドを使用してソートにかかる時間を計測します。

実行例（ Arrays.parallelSort：１億の要素を持つ配列を昇順にソート）

// ランダムな値（0 < 10000）をもつ、int型の配列（要素は100000000）を生成
int[] intArray = new Random().ints(100000000, 0, 10000).toArray();

Arrays.parallelSort( intArray ); // ソート

// 1回目：2.823秒
// 2回目：2.584秒
// 3回目：2.652秒

// ランダムな値（0 < 10000）をもつ、int型の配列（要素は100000000）を生成

int[] intArray = new Random().ints(100000000, 0, 10000).toArray();

Arrays.parallelSort( intArray ); // ソート

// 1回目：2.823秒

// 2回目：2.584秒

// 3回目：2.652秒

上記から、parallelSortメソッドを使用した方が、高速にソートできることが分かります。

parallelSortメソッドでは、ソートアルゴリズムに 並列ソートマージ を使用しているため、sort メソッドより、高速にソートすることができます。

注意点としては、ソートに必要な作業領域が、ソート対象の配列と同じ程度必要になります。