HOWTO · Java
Java で sort()メソッドを使わずに配列をソートする方法
sort()メソッドを使用せずに Java で配列をソートする方法を学ぶ
このページの内容
Java の配列は、Arrays.sort() を呼び出さなくても、要素を比較して自分で順番を入れ替えればソートできます。ソートの仕組みを学ぶときや、課題で手動実装が求められるときに役立ちます。Java の Arrays.toString() は配列を表示できますが、ソートはしません。
以下の例では、整数配列を昇順に並べ替えます。バブルソート、選択ソート、挿入ソートは動きを追いやすく、マージソートとクイックソートでは再帰的な分割統治の方法を紹介します。各コード例は単体で実行できる Java プログラムです。提供された実行証拠によると、5つの例はいずれも [11, 12, 22, 25, 34, 64, 90] という同じ結果になります。
Java で Arrays.sort() を使わずに配列をソートする
ソートアルゴリズムは、配列の要素が目的の順序になるまで、その位置を変更します。整数を昇順に並べる基本的な方法は、値を比較し、小さい値を大きい値より前に移動することです。以下のアルゴリズムは、それぞれ異なる方法でこの処理を行います。マージソートの実装ではマージ時に一時配列を使いますが、それ以外は入力配列をその場で変更します。
例として、{64, 34, 25, 12, 22, 11, 90} を {11, 12, 22, 25, 34, 64, 90} に並べ替えることを考えます。各実装では Arrays.sort() を意図的に使用していません。Arrays.toString() は配列を表示用の形式に整えるためだけに使います。
バブルソート
バブルソートは、隣り合う要素の組を繰り返し走査します。左側の値が右側より大きければ、両者を入れ替えます。1回の走査が終わると、未整列部分に残っている最大値がその末尾へ移動します。走査中に一度も入れ替えがなければ、swapped フラグによってループを早く終了します。最悪の場合の計算量は O(n²) なので、この実装は小さな入力やアルゴリズムの学習に向いています。
各コード例では Main というクラスを宣言しています。例を1つずつ Main.java として保存して実行してください。この例を実行します。
このセクションのコードと表示されるラベルや出力は英語のままです。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(values);
System.out.println(Arrays.toString(values));
}
static void bubbleSort(int[] values) {
for (int end = values.length - 1; end > 0; end--) {
boolean swapped = false;
for (int i = 0; i < end; i++) {
if (values[i] > values[i + 1]) {
int temp = values[i];
values[i] = values[i + 1];
values[i + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
}
[11, 12, 22, 25, 34, 64, 90]
選択ソート
選択ソートでは、配列を概念上、整列済みの先頭部分と残りの未整列部分に分けます。各走査で未整列部分から最小値を探し、それを未整列部分の先頭にある値と入れ替えます。たとえば、最初の走査では 11 を見つけてインデックス 0 に移し、次の走査では 12 を見つけてインデックス 1 に移します。初期状態にかかわらず比較回数は O(n²) ですが、入れ替えの回数は線形です。
このセクションのコードと表示されるラベルや出力は英語のままです。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {64, 34, 25, 12, 22, 11, 90};
selectionSort(values);
System.out.println(Arrays.toString(values));
}
static void selectionSort(int[] values) {
for (int i = 0; i < values.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < values.length; j++) {
if (values[j] < values[minIndex]) {
minIndex = j;
}
}
int temp = values[i];
values[i] = values[minIndex];
values[minIndex] = temp;
}
}
}
[11, 12, 22, 25, 34, 64, 90]
挿入ソート
挿入ソートは、左から右へ整列済みの先頭部分を広げていきます。次の値を key に保存し、先頭部分にあるそれより大きな値を1つ右へずらしてから、空いた位置に key を入れます。各走査の開始時点で、i より前の要素はすでに整列済みです。動きを追いやすく、小さな配列やほぼ整列済みの配列では有効な場合がありますが、最悪の場合の計算量は O(n²) です。
このセクションのコードと表示されるラベルや出力は英語のままです。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {64, 34, 25, 12, 22, 11, 90};
insertionSort(values);
System.out.println(Arrays.toString(values));
}
static void insertionSort(int[] values) {
for (int i = 1; i < values.length; i++) {
int key = values[i];
int j = i - 1;
while (j >= 0 && values[j] > key) {
values[j + 1] = values[j];
j--;
}
values[j + 1] = key;
}
}
}
[11, 12, 22, 25, 34, 64, 90]
マージソート
マージソートは配列を再帰的に半分ずつ分割し、各部分が1つの値になるまで続けた後、整列済みの部分配列をマージします。マージ中は2つのインデックスで各半分の次の未使用値を追跡し、小さい方の値を先に結果へコピーします。値が等しい場合に左側の値を選ぶため、元の相対順序が保たれます。この実装の計算量は O(n log n) で、再帰中に一時配列を割り当てるため、入力サイズに比例する追加メモリを使います。
このセクションのコードと表示されるラベルや出力は英語のままです。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {64, 34, 25, 12, 22, 11, 90};
mergeSort(values);
System.out.println(Arrays.toString(values));
}
static void mergeSort(int[] values) {
if (values.length < 2) {
return;
}
int middle = values.length / 2;
int[] left = Arrays.copyOfRange(values, 0, middle);
int[] right = Arrays.copyOfRange(values, middle, values.length);
mergeSort(left);
mergeSort(right);
merge(values, left, right);
}
static void merge(int[] values, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
values[k++] = left[i++];
} else {
values[k++] = right[j++];
}
}
while (i < left.length) values[k++] = left[i++];
while (j < right.length) values[k++] = right[j++];
}
}
[11, 12, 22, 25, 34, 64, 90]
クイックソート
クイックソートはピボットを選び、現在の範囲を分割して、ピボットより小さい値を前に、それ以外の値を後ろに配置します。この実装では範囲の最後の値をピボットにします。分割処理はピボットの最終インデックスを返し、再帰呼び出しでその左右の範囲をそれぞれソートします。クイックソートの計算量は通常 O(n log n) ですが、すでに整列済みのデータなど、入力によってはこのピボット選択で O(n²) になることがあります。再帰呼び出しにはスタック領域も必要です。
このセクションのコードと表示されるラベルや出力は英語のままです。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {64, 34, 25, 12, 22, 11, 90};
quickSort(values, 0, values.length - 1);
System.out.println(Arrays.toString(values));
}
static void quickSort(int[] values, int low, int high) {
if (low >= high) {
return;
}
int pivotIndex = partition(values, low, high);
quickSort(values, low, pivotIndex - 1);
quickSort(values, pivotIndex + 1, high);
}
static int partition(int[] values, int low, int high) {
int pivot = values[high];
int smallerEnd = low - 1;
for (int current = low; current < high; current++) {
if (values[current] < pivot) {
smallerEnd++;
int temp = values[smallerEnd];
values[smallerEnd] = values[current];
values[current] = temp;
}
}
int pivotIndex = smallerEnd + 1;
int temp = values[pivotIndex];
values[pivotIndex] = values[high];
values[high] = temp;
return pivotIndex;
}
}
[11, 12, 22, 25, 34, 64, 90]
アルゴリズムの選び方とトレードオフ
学習や小さな配列のソートでは、バブルソート、選択ソート、挿入ソートを使うと比較や値の移動を確認しやすくなります。ただし、計算量が二乗で増えるため、大きな入力には適しません。挿入ソートは、配列が小さい場合や、ほぼ整列済みの場合に向いています。選択ソートは、各走査で最大1回しか値を入れ替えないため、書き込み回数を抑えたい場合に使えることがあります。ただし、毎回残りの値を走査する必要があります。
マージソートは計算量が O(n log n) と予測しやすく、安定した順序が必要な場合に適していますが、この実装では一時配列を割り当てます。クイックソートは一般に高速で、元の配列内でソートします。一方、この末尾要素をピボットにする実装には、最悪時の二乗の計算量と再帰によるスタック使用があります。本番コードでは、手動アルゴリズムが明示的に必要でない限り、Java の標準ライブラリのソートを使うのが適切です。通常のプリミティブ配列のソートには Arrays.sort() を使い、手動アルゴリズムの動作や制約が課題となる場合に、その仕組みを学んだり実装したりしてください。
