Javaでデータの整列を実装する

基本情報技術者試験に向けてアルゴリズムを勉強しています。今回はデータの整列を代表する5つのアルゴリズムについてまとめます。

標準ライブラリでのソート

自分でソートのアルゴリズムを実装する前に、標準ライブラリで用意されているソートを利用してみましょう。標準ライブラリでは、java.utilパッケージに含まれるArraysクラスを用いて配列のソートを行うことができます。

  • static void sort(int[] a)
    指定された配列を数値の昇順でソート

実際に利用してみましょう。クラスを作成し、以下のプログラムを記述、実行してください。

import java.util.Arrays;

public class Sample {
    public static void main(String[] args) {
        int[] array = {11, 3, 28, 14, 23, 7, 4, 1, 5, 20};

        Arrays.sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ", ");
        }
    }
} 

実行結果は以下のようになります。Arrays.sortメソッドを呼び出すことで渡した配列が昇順に並び替えられていることがわかります。

1, 3, 4, 5, 7, 11, 14, 20, 23, 28,

バブルソート

バブルソートは隣り合う要素を比較し、順序が逆なら入れ替えを行うアルゴリズムです。バブルソートのバブルは、泡が浮かび上がるように大きな要素が後ろに移動していく様から名づけられています。

具体的に考えてみましょう。昇順に並べるとします。まず、a[0]とa[1]ですが、a[0] > a[1]と大小が逆になっているので入れ替えます。

82101

次にa[1]とa[2]を比較するとa[1] < a[2]なので入れ替えは行いません。その後、a[2]とa[3]、a[3]とa[4]と比較、必要に応じて入れ替えを行っていきます。今回の例の場合、「28」が最大要素なので、一回のステップごとに次第に配列の最後に移動していくことになります。

82102

これで、最大要素が確定しました。続いて、もう一度a[0]とa[1]、a[1]とa[2]と比較、入れ替えを行うとa[8]に二番目に大きな要素「23」が格納されます。なお、比較、入れ替え処理はa[7]とa[8]までを行えばいいことになります。(a[9]はすでに最大要素が入っているので入れ替えは発生しえないからです)

さらに繰り返しを行うと配列の後ろの方から要素が確定していき、最終的に昇順に並び替えられることになります。

バブルソートを実装する

それではバブルソートを実現するプログラムを作成しましょう。メソッドの引数と戻り値は標準ライブラリのArrays.sortメソッドに合わせて以下の通りとします。

  • static int bubbleSort(int[] a)
    指定された配列を数値の昇順でソート

BubbleSortクラスを作成し、以下のメソッドを記述してください。

public class BubbleSort {
	public static void bubbleSort(int[] a) {
		for(int i = 0; i + 1 < a.length; i++) {
			for(int j = 0; j + 1 < a.length - i; j++) {
				if(a[j] > a[j + 1]) {
					int tmp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = tmp;
				}

				// 確認のために配列を出力
				for (int k = 0; k < a.length; k++) {
					System.out.print(a[k] + ", ");
				}
				System.out.println();
			}
			System.out.println("----------------");
		}
    }
}

動作確認

動作確認用のクラスを作成し、mainメソッドに以下の内容を記述します。

public static void main(String[] args) {
    int[] array = {11, 3, 28, 14, 23, 7, 4, 1, 5, 20};

    BubbleSort.bubbleSort(array);
}

実行結果

3, 11, 28, 14, 23, 7, 4, 1, 5, 20, 
3, 11, 28, 14, 23, 7, 4, 1, 5, 20, 
3, 11, 14, 28, 23, 7, 4, 1, 5, 20, 
3, 11, 14, 23, 28, 7, 4, 1, 5, 20, 
3, 11, 14, 23, 7, 28, 4, 1, 5, 20, 
3, 11, 14, 23, 7, 4, 28, 1, 5, 20, 
3, 11, 14, 23, 7, 4, 1, 28, 5, 20, 
3, 11, 14, 23, 7, 4, 1, 5, 28, 20, 
3, 11, 14, 23, 7, 4, 1, 5, 20, 28, 
----------------
3, 11, 14, 23, 7, 4, 1, 5, 20, 28, 
3, 11, 14, 23, 7, 4, 1, 5, 20, 28, 
3, 11, 14, 23, 7, 4, 1, 5, 20, 28, 
3, 11, 14, 7, 23, 4, 1, 5, 20, 28, 
3, 11, 14, 7, 4, 23, 1, 5, 20, 28, 
3, 11, 14, 7, 4, 1, 23, 5, 20, 28, 
3, 11, 14, 7, 4, 1, 5, 23, 20, 28, 
3, 11, 14, 7, 4, 1, 5, 20, 23, 28, 
----------------
3, 11, 14, 7, 4, 1, 5, 20, 23, 28, 
3, 11, 14, 7, 4, 1, 5, 20, 23, 28, 
3, 11, 7, 14, 4, 1, 5, 20, 23, 28, 
3, 11, 7, 4, 14, 1, 5, 20, 23, 28, 
3, 11, 7, 4, 1, 14, 5, 20, 23, 28, 
3, 11, 7, 4, 1, 5, 14, 20, 23, 28, 
3, 11, 7, 4, 1, 5, 14, 20, 23, 28, 
----------------
〜 中略 〜
1, 3, 4, 5, 7, 11, 14, 20, 23, 28, 
1, 3, 4, 5, 7, 11, 14, 20, 23, 28, 
----------------
1, 3, 4, 5, 7, 11, 14, 20, 23, 28, 
----------------

バブルソートの解説

コードを読むだけではアルゴリズムの仕組みが分かりにくいと思います。今回は実際にアルゴリズムを実装する工程を追いかけてみましょう。今回はクラスやメソッドの宣言方法は省略します。

このアルゴリズムは主に4つの工程で作成します。

  1. 内側のfor文を組み立てる
  2. if文を組み立てる
  3. 外側のfor文を組み立てる
  4. 内側のfor文の無駄を省く

それでは順番に見ていきましょう。

  1. 内側のfor文を組み立てる

内側のfor文を書きます。a.lengthが分からないでしょうか?これは配列の要素数を返すプロパティです。配列の全要素を調べるためにこのような書き方をします。
jが「配列の現在の要素」でj + 1が「配列の次の要素」にあたります。このあとのif文ではa[j]a[j + 1]を比較して入れ替えます。なので、for文の終了条件はj + 1 < a.lengthになります。隣同士を入れ替えるのだから「配列の次の要素」が「配列の最後」に到達すれば終了しても良いということになります。

for(int j = 0; j + 1 < a.length; j++) {
}
  1. if文を組み立てる

if文を書き足します。a[j]が「配列の現在の要素」でa[j + 1]が「配列の次の要素」です。これらを比較して、「配列の現在の要素」のほうが大きかった場合は「配列の次の要素」と入れ替えます。入れ替える際にはtmp変数を使用して、値を一時的な保存場所に移動しながら行います。

for(int j = 0; j + 1 < a.length; j++) {
    if(a[j] > a[j + 1]) {
        int tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
    }
}
  1. 外側のfor文を組み立てる

外側のfor文を書き足します。混乱を避けるためにfor文の役割をもう一度確認しましょう。内側のfor文は「順々に隣同士の要素を比較して要素同士を入れ替える処理」です。これを一度行っただけでは、一番大きい要素が配列の最後に置かれるだけです。対して、外側のfor文は「内側のfor文を配列の要素数分繰り返す処理」になります。配列の要素数分同じことを繰り返すことで、すべての要素が小さい順に整列します。

for(int i = 0; i + 1 < a.length; i++) {
    for(int j = 0; j + 1 < a.length; j++) {
        if(a[j] > a[j + 1]) {
            int tmp = a[j];
            a[j] = a[j + 1];
            a[j + 1] = tmp;
        }
    }
}
  1. 内側のfor文の無駄を省く

3.の時点では内側のfor文には無駄な処理が含まれています。内側のfor文のループ条件をj + 1 < a.length - iに修正しましょう。どうして配列の要素数から変数iを引くのかを考えてみます。外側のfor文が回るごとにiが加算され、配列内で一番大きい数値が配列の一番最後に配置されます。つまり、配列の最後の要素から順番に確定していくので、その部分に関しては比較処理を行わなくても良いということになります。

for(int i = 0; i + 1 < a.length; i++) {
    for(int j = 0; j + 1 < a.length - i; j++) {
        if(a[j] > a[j + 1]) {
            int tmp = a[j];
            a[j] = a[j + 1];
            a[j + 1] = tmp;
        }
    }
}

これでバブルソートが完成しました。

バブルソートの計算量

バブルソートのアルゴリズムをフローチャートで書くと以下のようになります。(配列をa、配列の大きさをnとします)

82104

一番初めのバブルソートのソースコードでは確認のために配列の出力を行っています。jのループが終わるごとに区切り線を出力しているので、区切り線が現れるまでの行数を数えてみると、以下のようになります。これはつまり、フローチャートのループ1が回るごとにループ2が回る回数が1回ずつ減っていくということです。

$9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45$

9から1まで足すというのを一般化すると、配列の大きさをnに対して、比較の回数はn * (n + 1) / 2回になります。
なぜ、n * (n + 1) / 2になるのでしょうか。単純に1から9までを順番に足していくのではなく、以下のように2つの連続した数を用意し、上下で足し算をします。9組の10という数値を作るという考え方です。9 * 10は90なので、これを半分に割ると求めたかった45という値になります。余談になりますが、この計算方法は数学者ガウスが少年時代に考案したものです。

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9
               +
9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1

n * (n + 1) / 2を計算量オーダーに直すために、最高次数以外の項を無視すると、$n(n)$になります。次数とは掛け合わされている項の数です。今回、一番多い次数はnなので、nが最高次数になります。ここから$n(n)$を変形させて、O記号を付けると計算量オーダーになります。つまり、計算量オーダーは$O(n^2)$になります。

$O(n^2)$の計算量はデータの大きさが10倍になると実行時間が100倍になります。実際、配列が100要素あるとすると、100 * 99 / 2 = 4950と100倍以上の比較回数が必要なことがわかります。このため、バブルソートはソートアルゴリズムの手始めとしては使われますが、実用的なプログラムでのソート処理にはほとんど使われません。

選択ソート

選択ソートは配列の中から最小の要素を探索し、それを配列の先頭と入れ替えることでソートを行うアルゴリズムです。

例によって具体的に考えてみましょう。まず、a[0]を最小とみなします。

83101

a[0]とa[1]を比較するとa[1]の方が小さいので最小値を更新します。

83102

以降は最小値のa[1]とa[2]以降を比較していきます。結果、a[7]が最小なことがわかります。

83103

a[7]が最小なことがわかったので、a[7]とa[0]を入れ替えます。これでa[0]に最小値が入りました。

83104

a[0]は確定したので、次はa[1]を最小とみなしてa[2]~a[9]と比較していきます。今回はa[1]より小さいものはないので入れ替えは行われません。

83105

続いて、a[2]、a[3]、と確定していくと、最終的に昇順に並び替えられることになります。

選択ソートを実装する

それでは選択ソートを実現するプログラムを作成しましょう。メソッドの引数と戻り値は標準ライブラリのArrays.sortメソッドに合わせて以下の通りとします。

  • static int selectionSort(int[] a)
    指定された配列を数値の昇順でソート

SelectionSortクラスを作成し、以下のメソッドを記述してください。

public class SelectionSort {
	public static void selectionSort(int[] a) {
		for(int i = 0; i < a.length; i++) {
			int min = i;
			for(int j = i + 1; j < a.length; j++) {
				if (a[min] > a[j]) {
					// 最小値を選択(更新)する
					min = j;
				}
			}

			if (i != min) {
				// 配列の現在要素と最小値を入れ替える
				int tmp = a[i];
				a[i] = a[min];
				a[min] = tmp;
			}

			// 確認のために配列を出力
			for (int k = 0; k < a.length; k++) {
				System.out.print(a[k] + ", ");
			}
			System.out.println();
		}
	}
}

動作確認

動作確認用のクラスを作成し、mainメソッドに以下の内容を記述します。

public static void main(String[] args) {
    int[] array = {11, 3, 28, 14, 23, 7, 4, 1, 5, 20};

    SelectionSort.selectionSort(array);
}

実行結果

1, 3, 28, 14, 23, 7, 4, 11, 5, 20, 
1, 3, 28, 14, 23, 7, 4, 11, 5, 20, 
1, 3, 4, 14, 23, 7, 28, 11, 5, 20, 
1, 3, 4, 5, 23, 7, 28, 11, 14, 20, 
1, 3, 4, 5, 7, 23, 28, 11, 14, 20, 
1, 3, 4, 5, 7, 11, 28, 23, 14, 20, 
1, 3, 4, 5, 7, 11, 14, 23, 28, 20, 
1, 3, 4, 5, 7, 11, 14, 20, 28, 23, 
1, 3, 4, 5, 7, 11, 14, 20, 23, 28, 
1, 3, 4, 5, 7, 11, 14, 20, 23, 28, 

選択ソートの解説

コードを読むだけではアルゴリズムの仕組みが分かりにくいと思います。今回は実際にアルゴリズムを実装する工程を追いかけてみましょう。今回はクラスやメソッドの宣言方法は省略します。

  1. 外側のfor文を組み立てる
  2. 内側のfor文を組み立てる
  3. 最小値を選択する処理を組み立てる
  4. 配列の現在要素と最小値を入れ替える処理を組み立てる

それでは順番に見ていきましょう。

  1. 外側のfor文を組み立てる

外側のfor文を組み立てます。選択ソートでは先頭の要素から順番に最小値として確定していきます。ここでのiは最小値として確定させたい要素を指しています。int min = iとして新たにminという選択用の変数を作ります。minは最小値と思われる要素番号を一時的に保存しておく変数です。最終的にはa[i]に最小値が格納されます。

for(int i = 0; i < a.length; i++) {
	int min = i;
}
  1. 内側のfor文を組み立てる

内側のfor文を組み立てます。int j = i + 1として、確定させたい先頭要素(a[i])の次の要素から順番に調べていきます。a[i]より前の要素は既に最小値として確定しているため、調べる必要はありません。

for(int i = 0; i < a.length; i++) {
	int min = i;
    for(int j = i + 1; j < a.length; j++) {
    }
}
  1. 最小値を選択する処理を組み立てる

内側のfor文の中にif文を書き足します。変数minの要素番号を次々入れ替えていきます。より小さい要素が現れたときに、変数minにその要素番号を格納します。

for(int i = 0; i < a.length; i++) {
	int min = i;
    for(int j = i + 1; j < a.length; j++) {
        if (a[min] > a[j]) {
            min = j;
        }
    }
}
  1. 配列の現在要素と最小値を入れ替える処理を組み立てる

外側のfor文にif文を書き足します。先頭要素(i)が最小値ではない場合にa[i]a[min]を入れ替えます。入れ替える際にはtmp変数を使用して、値を一時的な保存場所に移動しながら行います。

for(int i = 0; i < a.length; i++) {
	int min = i;
    for(int j = i + 1; j < a.length; j++) {
        if (a[min] > a[j]) {
            min = j;
        }
    }
    
    if (i != min) {
        // 最小値を入れ替え
        int tmp = a[i];
        a[i] = a[min];
        a[min] = tmp;
    }
}

これで選択ソートが完成しました。

選択ソートの計算量

選択ソートのアルゴリズムをフローチャートで書くと以下のようになります。(配列をa、配列の大きさをnとします)

83106

初めに紹介したバブルソートのアルゴリズムと比較してみると、処理が似通っていることが分かると思います。バブルソートではループ1が回るごとに配列の最後の要素から順番に確定していき、ループ2が回る回数が1ずつ減っていきました。選択ソートではループ1が回るごとに配列の最初の要素から順番に確定していき、ループ2が回る回数が1ずつ減っていきます。つまり、n * (n + 1) / 2回の比較が必要になります。そのため、バブルソートと同じく$O(n^2)$の計算量になります。

選択ソートではループ2が終わった後に1回だけ入れ替えが行われます。そのため、入れ替え回数は最大で$n - 1$回になります。バブルソートは大小が逆になっていると毎回入れ替えていたことを思い出してください。

このように選択ソートはバブルソートに比べて入れ替え回数が少なくなるため、バブルソートより高速になります。ただし、データの量が多くなった場合、比較回数についてはバブルソートと同様に二乗のオーダーで増加することになります。

挿入ソート

挿入ソートはソート済みの配列の適切な位置に要素を挿入することでソートを行うアルゴリズムです。
言葉だけではわかりにくいので具体例を考えます。

まず、1要素だけからなるソート済みの配列があるとします。(1要素だけなので、当然ソート済みです)

84101

ソート済みの配列に1要素(a[1])加えます。

84102

追加された要素を「適切な位置に」挿入します。今回の場合、a[1]よりa[0]の方が大きいので、a[0]a[1]の位置にずらして、a[1]の値をa[0]の位置に挿入します。

84103

これだけだとまだイメージがわかないと思うのでもう少し処理が進んだ状態を考えてみましょう。ここではa[4]までがソート済みでa[5]を追加するとします。

84104

この場合、a[5]の値「7」を挿入するには、a[1]a[4]を後ろにずらし、空いたa[1]の位置にa[5]の値を挿入します。

84105

a[6]以降も同じように適切な位置に挿入することで、最終的に全配列要素が昇順に並び替えられることになります。

挿入ソートを実装する

それでは挿入ソートを実現するプログラムを作成しましょう。メソッドの引数と戻り値は標準ライブラリのArrays.sortメソッドに合わせて以下の通りとします。

  • static int insertionSort(int[] a)
    指定された配列を数値の昇順でソート

InsertionSortクラスを作成し、以下のメソッドを記述してください。

public class InsertionSort {
    public static void insertionSort(int[] a) {
        //配列の1つ目の要素は確定済みとみなすのでiは1
        for (int i = 1; i < a.length; i++) {
            //挿入対象の要素を一時退避(保存)するtarget変数に入れておく
            int target = a[i];
            int j = i;

            // 挿入位置を決めると同時に挿入対象より大きい値を後ろにずらす
            while (j > 0 && a[j-1] > target) {
                a[j] = a[j-1];
                j--;
            }
            a[j] = target;

            // 確認のために配列を出力
            for (int k = 0; k < a.length; k++) {
                System.out.print(a[k] + ", ");
                if (k == i) {
                    System.out.print("| ");
                }
            }
            System.out.println();
        }
    }
}

動作確認

動作確認用のクラスを作成し、mainメソッドに以下の内容を記述します。

public static void main(String[] args) {
    int[] array = {11, 3, 28, 14, 23, 7, 4, 1, 5, 20};

    InsertionSortTest.insertionSort(array);
}

実行結果

3, 11, | 28, 14, 23, 7, 4, 1, 5, 20, 
3, 11, 28, | 14, 23, 7, 4, 1, 5, 20, 
3, 11, 14, 28, | 23, 7, 4, 1, 5, 20, 
3, 11, 14, 23, 28, | 7, 4, 1, 5, 20, 
3, 7, 11, 14, 23, 28, | 4, 1, 5, 20, 
3, 4, 7, 11, 14, 23, 28, | 1, 5, 20, 
1, 3, 4, 7, 11, 14, 23, 28, | 5, 20, 
1, 3, 4, 5, 7, 11, 14, 23, 28, | 20, 
1, 3, 4, 5, 7, 11, 14, 20, 23, 28, | 

今回は「|」を出力することで、どこまでがソート済みかがわかるようになっています。

挿入ソートの解説

コードを読むだけではアルゴリズムの仕組みが分かりにくいので、今回も実際にアルゴリズムを実装する工程を追いかけてみましょう。今回はクラスやメソッドの宣言方法は省略します。

  1. 外側のfor文を組み立てる
  2. 内側のwhile文を組み立てる
  3. 挿入対象を挿入する処理を書く

それでは順番に見ていきましょう。

  1. 外側のfor文を組み立てる

外側のfor文を組み立てます。int i = 1として配列の2つ目の要素から開始している理由は、2つ目の要素は最初の要素の左右どちらかに挿入するので、最初の要素は調べる必要がないということです。続いて、変数を用意していきます。
target変数は挿入対象の要素を一時的に保存しておく変数です。挿入対象が入っていた元々の要素空間は、挿入対象より大きい要素が1要素分ずつ後方にずれ込んでくるので、利用することができなくなります。この移動は挿入対象の要素が適切な位置に挿入される空間を空けるために行われます。
j変数はこの後のwhile文で使用します。

for (int i = 1; i < a.length; i++) {
    int target = a[i];
    int j = i;
}
  1. 内側のwhile文を組み立てる

内側のwhile文を組み立てます。j > 0 && a[j-1] > targetというループ条件を見ると難しく感じるので、1つずつ分けて考えましょう。
j > 0は繰り返し処理の終了条件です。j--によってマイナス方向に調べていくのは、今まで挿入してきた要素(挿入対象の要素よりも前にある要素)に対して、新たに対象要素を挿入するという処理を行うためです。
a[j-1] > targetは、今まで挿入してきた要素(挿入対象の要素よりも前にある要素)が挿入対象の要素よりも大きいかを調べています。大きい場合は、a[j] = a[j-1]を繰り返し実行していくのですが、これは挿入対象の要素を挿入する空間を空けるために1要素分ずつ後方に要素をずらしていく処理です。挿入対象の要素はtarget変数に一時保存しているので、挿入対象の要素を潰して1要素分後方にずらしても大丈夫ということですね。

for (int i = 1; i < a.length; i++) {
    int target = a[i];
    int j = i;
    
    while (j > 0 && a[j-1] > target) {
        a[j] = a[j-1];
        j--;
    }
}
  1. 挿入対象を挿入する処理を書く

target変数に一時保存していた挿入対象の要素を挿入します。事前にwhile文で要素が整列されているので、a[j] = targetという単純な挿入になります。a[j] = targetを行う時点で、既にa[0] 〜 a[n]まで小さい順に整列されています。while文のa[j-1] > targetという条件によって、挿入するために適切な要素番号をjが指すようになっています。

for (int i = 1; i < a.length; i++) {
    int target = a[i];
    int j = i;
    
    while (j > 0 && a[j-1] > target) {
        a[j] = a[j-1];
        j--;
    }
    
    a[j] = target;
}

これで挿入ソートが完成しました。

挿入ソートの計算量

挿入ソートのアルゴリズムをフローチャートで書くと以下のようになります。(配列をa、配列の大きさをnとします)

84106

挿入ソートの計算量を考えます。挿入ソートは単純な二重ループではないため、少し複雑になります。
まず、内側のwhileループがもっとも「回らない」場合を考えてみましょう。どのような場合にもっとも回らないでしょうか。

正解としては以下のような、「始めからソートされている配列」の場合、ループ回数が最小になります。

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

この場合、「a[j-1] > t」の条件がいきなり成り立たなくなります。つまり、ループが実行されることはなく、計算量は$O(n)$になります。(外側のn回分のループだけになるからです)

逆にもっとも「回る」場合はどういう場合でしょうか。以下のように、「ソートしたい順序の逆順にソートされている配列」の場合、ループ回数が最大になります。

{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}

この場合、配列をずらす回数は、1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45回になります。この数字はバブルソートと同じで$O(n2)$の計算量になります。

計算量オーダーについて考えるときは、最悪のケースを想定します。したがって計算量オーダーは$O(n2)$になります。

ただし、バブルソートではどのようなデータに対しても固定回数の比較が必要でしたが、挿入ソートでは挿入位置が決まった時点でループを打ち切るのでバブルソートよりも比較回数が少なくなります。また、ほぼソート済みの場合、比較や配列をずらす回数は少なくなり、高速にソートが行えます。

クイックソート

クイックソートは配列の分割を繰り返すことでソートを行うアルゴリズムです。
クイックソートの動作について見ていきましょう。まず、ソート対象の配列の中からピボットと呼ばれる値を選択します。今回は配列の第1要素をピボットとします。

85101

ピボット以下の値を配列の前方、ピボット以上の値を配列の後方に移動させます。具体的なアルゴリズムについては後述します。

85102

ピボット以下の配列に対して改めてピボットを選び入れ替え、ピボット以上の配列に対して同様に入れ替えを行います。

85103

最終的に各配列の要素数が1つだけになるまで繰り返します。

85104

要素1つずつに分かれた配列を確認してください。昇順に並んでいることがわかります。このようにクイックソートではピボットを基準に要素の入れ替えを繰り返すことにより、ソートが行われます。その際に重要なのが分割統治という考え方です。

分割統治とは具体例で見てきたように全体の配列を一度に処理するのではなく、二つに分割する、さらに二つに分割する、を繰り返して問題をより細かくしていき、最終的に問題全体を解決する(今回の場合、配列を並び替える)考え方です。仕事などでも仕事全体は量が多くて大変でも、それを細かく分けてひとつずつこなしていけば最終的に全部の仕事を完了できるというイメージです。

クイックソートで鍵となるのは、ピボット以下の配列とピボット以上の配列に分割する処理です。これについてより具体的に見ていきましょう。

配列を先頭から見るiと末尾から見るjを用意します。

85105

iは先頭からピボット以上の数字を、jは末尾からピボット以下の数字を探します。今回はiとしてa[0]jとしてa[8]が選択されます。

85106

iで選択されている要素とjで選択されている要素を入れ替えます。

85107

iを一つ右、jを一つ左に移動したうえで同様にiはピボット以上、jはピボット以下の数字を探します。今度はiとしてa[2]jとしてa[7]が選択されます。

85108

a[2]a[7]の入れ替えを行い、i, jをさらに進め入れ替えを行います。最終的に、以下のようにijが交差します。

85109

この状態になったら、分割は完了です。iの左側を見るとピボット以下の数値、jの右側を見るとピボット以上の数値だけになっていることがわかります。

85110

分割が行えたら次は、a[0]~a[i-1]、a[j+1]~a[9]それぞれについて同じ処理を行うとさらに分割が行われ、最終的に要素1つずつの配列まで分割を行うと全体の配列が並び替えられた状態になります。

同じ処理、と書きましたが具体的には範囲を狭めた配列を引数にして再帰呼び出しを行います。

次の項に進む前に{23, 14, 28, 11, 20}(分割されたピボット以上の配列)について、正しくピボット以下の配列、ピボット以上の配列に分割されることを確認してください。({20, 14, 11}と{28, 23}に分割されます)

クイックソートを実装する

それではクイックソートを実現するプログラムを作成しましょう。メソッドの引数と戻り値は標準ライブラリのArrays.sortメソッドに合わせて以下の通りとします。

  • static int quickSort(int[] a)
    指定された配列を数値の昇順でソート

QuickSortクラスを作成し、以下のメソッドを記述してください。

public class QuickSort {
    public static void quickSort(int[] a) {
        quickSort(a, 0, a.length-1);
    }

    private static void quickSort(int[] a, int left, int right) {
        // 渡された配列を表示
        System.out.print("l=" + left + "\tr=" + right + "\t");
        for (int k = left; k <= right; k++) {
            System.out.print(a[k] + ", ");
        }
        System.out.println();

        // ピボットを基準に配列を2つに分割
        int pivot = a[left];
        int i = left;
        int j = right;
        while (true) {
            // ピボット以上を探す
            while (a[i] < pivot) {
                i++;
            }
            // ピボット以下を探す
            while (pivot < a[j]) {
                j--;
            }
            // 左からのチェックが右を踏み越えたら終了
            if (i >= j) {
                break;
            }
            // 入れ替えて次を探す
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
        }

        // ピボットを基準に分割された配列を表示
        // iの左側はピボット以下、右側はピボット以上になる
        System.out.print("\t\t");
        for (int k = left; k <= right; k++) {
            System.out.print(a[k] + ", ");
            if (k == i - 1) {
                System.out.print("| ");
            }
        }
        System.out.println();

        // 分割された配列が3要素以上の場合、再帰呼び出しを行ってソート
        if (left < i - 1) {
            quickSort(a, left, i - 1);
        }
        if (j + 1 < right) {
            quickSort(a, j + 1, right);
        }

        // 渡された部分配列に対する最終結果を表示
        System.out.print("result\t\t");
        for (int k = left; k <= right; k++) {
            System.out.print(a[k] + ", ");
        }
        System.out.println();
    }
}

メソッドは外部から呼ばれるpublicメソッドと内部処理のprivateメソッドに分かれています。publicメソッドでは配列全体を対象にクイックソートのメイン処理を呼び出しています。

privateメソッドでは、前項で解説した分割処理を行い、分割されたピボット以下の配列、ピボット以上の配列について再帰呼び出しを行っています。なお、前項では1要素になるまで再帰呼び出しを行うとお話ししましたが、2要素までいけば順番に並ぶため、3要素以上の場合のみ再帰呼び出しを行っています。

動作確認

動作確認用のクラスを作成し、mainメソッドに以下の内容を記述します。

public static void main(String[] args) {
    int[] array = {11, 3, 28, 14, 23, 7, 4, 1, 5, 20};

    QuickSort.quickSort(array);
}

動作結果(quickSortメソッド内部で並び替え状況が出力されています)

l=0 r=9 11, 3, 28, 14, 23, 7, 4, 1, 5, 20,
5, 3, 1, 4, 7, | 23, 14, 28, 11, 20,
l=0 r=4 5, 3, 1, 4, 7,
4, 3, 1, | 5, 7,
l=0 r=2 4, 3, 1,
1, 3, | 4,
l=0 r=1 1, 3,
1, 3,
result 1, 3,
result 1, 3, 4,
l=3 r=4 5, 7,
5, 7,
result 5, 7,
result 1, 3, 4, 5, 7,
l=5 r=9 23, 14, 28, 11, 20,
20, 14, 11, | 28, 23,
l=5 r=7 20, 14, 11,
11, 14, | 20,
l=5 r=6 11, 14,
11, 14,
result 11, 14,
result 11, 14, 20,
l=8 r=9 28, 23,
23, | 28,
result 23, 28,
result 11, 14, 20, 23, 28,
result 1, 3, 4, 5, 7, 11, 14, 20, 23, 28,

引数のleft、right、分割前の配列、分割後の配列、再帰呼び出しを行った後の配列が表示されています。少し分かりにくいですが、配列が前の方からソートされていっている様子が確認できます。(再帰呼び出しは前の方が終わった後に後ろの方が行われます)

クイックソートの解説

コードを読むだけではアルゴリズムの仕組みが分かりにくいので、今回も実際にアルゴリズムを実装する工程を追いかけてみましょう。長いですが、やっていることは簡単なので心配しないでください。再帰呼び出し処理に抵抗感がある場合は、フィボナッチ数を出力するプログラムなどを再帰呼び出しで書いて、慣れておくことをお勧めします(再帰呼び出しにより作成される二分木の処理順序に慣れてください)。

  1. 再帰呼び出しを行うためにオーバーロードしたメソッドを作成する
  2. ピボットを選択する
  3. 左右からiとjでピボット値以上・以下を比較し、入れ替える
  4. 再帰呼び出し

それでは順番に見ていきましょう。

  1. 再帰呼び出しを行うためにオーバーロードしたメソッドを作成する

再帰呼び出しで処理を行うための前準備として、再帰呼び出し用のメソッドを作る必要があります。以下のようにmainメソッドから直接使用されるメソッドと再帰呼び出しで使用されるメソッドを分けましょう。

public static void quickSort(int[] a) {
    quickSort(a, 0, a.length - 1);
}

private static void quickSort(int[] a, int left, int right) {
}
  1. ピボットを選択する

ピボットを選択する処理を追記します。再帰呼び出しされるため、leftrightとして左側・右側からピボット値と比較する配列番号を受け取り、ijに代入します。ピボット値はleftが指す配列番号に格納された数値になります。

public static void quickSort(int[] a) {
    quickSort(a, 0, a.length - 1);
}

private static void quickSort(int[] a, int left, int right) {
    int pivot = a[left];
    int i = left;
    int j = right;
}
  1. 左右からiとjでピボット値以上・以下を比較し、入れ替える

while文の大きなブロックを追記します。少し長いですが、順番に解説します。iは配列を左側から調べます。左側にはピボット値よりも小さな値を集めるので、ピボット値以上の値が見つかったらjの配列番号が指すフィールドと入れ替えます。対して、jは配列を右側から調べます。右側にはピボット値よりも大きな値を集めるので、ピボット値以下の値が見つかったらiの配列番号が指すフィールドと入れ替えます。順番に調べていき、ijの指す配列番号が交差したら入れ替え処理を終了します。

public static void quickSort(int[] a) {
    quickSort(a, 0, a.length - 1);
}

private static void quickSort(int[] a, int left, int right) {
    int pivot = a[left];
    int i = left;
    int j = right;
    
    while (true) {
        // ピボット以上を探す
        while (a[i] < pivot) {
            i++;
        }
        // ピボット以下を探す
        while (pivot < a[j]) {
            j--;
        }
        // 左からのチェックが右を踏み越えたら終了
        if (i >= j) {
            break;
        }
        // 入れ替えて次を探す
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        i++;
        j--;
    }
}
  1. 再帰呼び出し

再帰呼び出し処理を追記します。2つの再帰呼び出し処理を行うことで、二分木を形成します。問題を二分していき、最小まで分けたところで問題を解決します。これはよく使われる計算パターンで、木構造再帰(tree recursion)と呼ばれています。
分割された配列が3要素以上の場合、再帰呼び出しを行ってソートを行います。どうして3要素以上なのかというと、3要素は要素数2:1に分割され、要素数2側のソートが行われます。この時点で問題は最小まで分割されており、解決済みです。

public static void quickSort(int[] a) {
    quickSort(a, 0, a.length - 1);
}

private static void quickSort(int[] a, int left, int right) {
    int pivot = a[left];
    int i = left;
    int j = right;
    
    while (true) {
        // ピボット以上を探す
        while (a[i] < pivot) {
            i++;
        }
        // ピボット以下を探す
        while (pivot < a[j]) {
            j--;
        }
        // 左からのチェックが右を踏み越えたら終了
        if (i >= j) {
            break;
        }
        // 入れ替えて次を探す
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        i++;
        j--;
    }

    // 分割された配列が3要素以上の場合、再帰呼び出しを行ってソート
    if (left < i - 1) {
        quickSort(a, left, i - 1);
    }
    if (j + 1 < right) {
        quickSort(a, j + 1, right);
    }
}

これでクイックソートが完成しました。

クイックソートの計算量

クイックソートの計算量を考えましょう。今回の計算量では、対数(log)が登場します。読む前に、指数・対数についての知識を身に付けることをお勧めします。

クイックソートは配列を分割することによりソートを行います。理想的な状況では配列は毎回、半分ずつに分割されます。半分ずつになる、と聞いて二分探索を連想された方がいるかもしれません。二分探索では、理想的な状況では再帰呼び出しの回数は$log_2n$回となります。例えば、配列の要素数が10であれば、4回($2^4 = 16$)、100であれば7回($2^7 = 128$)になります。(要素数が10の場合は 10 → 5 → 3 → 2 → 1のように、要素数を最小に分割するためには4回割る必要があるということです。)

一方、クイックソートでは再帰呼び出しで配列の全要素を調べる必要があります。これにはn回(全要素数分)の比較が必要になります。結果、クイックソートは$O(nlog_2n)$の計算量が必要になります。

理屈としては、二分探索では既に昇順にソート済みの配列を探索するので、全ての要素と比較する必要はありません。しかし、クイックソートでは対象の配列はソートされていないので、再帰呼び出しで二分していきながら、全ての要素に対して比較が行われるということです。つまり、n回の比較 × $log_2n$回の再帰呼び出し(による比較)を行うので$O(nlog_2n)$の計算量になります。

$O(nlog_2n)$という計算量はどのような値でしょうか。具体的に計算してみましょう。

n=100の場合:100 * $log_{2}100$ < 100 * 7 = 700
n=1000の場合:1000 * $log_{2}1000$ < 1000 * 10 = 10000
n=10000の場合: 1000 * $log_{2}10000$ < 10000 * 14 = 140000

データ量が100倍になっても、計算量は200倍で収まっています。バブルソートなど、$O(n^2)$の計算量がかかるソートの場合、データ量が100倍になると計算量が10000倍になっていたわけですからクイックソートはデータ量が増加しても高速に実行できることがわかります。このように$O(nlog_2n)$の計算量は非常に優れていることがわかります。

最悪の場合は、配列が、毎回1個とn-1個に分割される場合です。この場合、再帰呼び出しの回数はn回(全要素数分)になります。n回の比較とn回の再帰呼び出しが必要なことから計算量は$O(n^2)$になります。

最悪の呼び出し回数になるのはどのような場合でしょうか。正解は以下のように「すでにソートされている配列」です。実際に1要素と残り、というように分割されることを確認してください。

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

このようになるのはピボットとして、配列の左端を選んでいるためです。ピボットを工夫することにより、確率的に最悪の状況を回避することが可能になります。(例えば、配列中のランダムな値を選択する、3要素を抜き出してその中から中央値を選択するなど)

マージソート

マージソートはソート済みの複数の配列をマージする際に小さい順に新規配列に加えることでマージ後の配列もソートされたものになるという発想のソートアルゴリズムです。

具体的に見てみましょう。次の2つの配列があるとします。この2つの配列を1つの配列にまとめることをマージと言います。

86101

マージを行う際、配列a、配列bの要素を先頭から見ていき、小さい方をマージ後の配列cの先頭要素とします。具体的には、a[0] > b[0]なので、b[0]c[0]とします。

86102

次にa[0]b[1]を比較します。a[0] < b[1]なので今度はa[0]c[1]として追加します。

86103

次はa[1] > b[1]なのでb[1]c[2]として追加します。

86104

配列bは最後まで行ったので、配列aの残り、a[1]c[3]として追加します。これでマージが行えました。配列cを見ると昇順に並んでいることがわかります。

86105

マージの際に追加順序を考慮することでソートを行えることはわかりました。次に、ある配列を与えられた場合にどのようにマージソートを適用するかを考えます。

86106

答えとしては、配列を分割します。クイックソートのようにピボットで分けるのではなく、配列の真ん中で区切ります。

86107

この時点では分割した配列a1、a2はソートされた状態ではありませんが、さらに分割を繰り返し、要素が1つだけの配列まで分割を行います。

86108

要素が1つだけになればその配列は必ずソート済みです。ここまで分割したら今度は逆に小さい順にマージを行っていきます。

86109

これでソートが行えました。なお、配列の分割からマージまでを合わせて、マージソートと呼ばれています。

整理するとマージソートのアルゴリズムは以下のようになります。

  1. 配列を分割する
  2. 配列をソートする
  3. ソートされた配列をマージする

2.の「配列をソートする」ではマージソートの再帰呼び出しを行います。再帰呼び出しは配列の要素が1つになったら停止するようにします。

マージソートを実装する

それではマージソートを実現するプログラムを作成しましょう。メソッドの引数と戻り値は標準ライブラリのArrays.sortメソッドに合わせて以下の通りとします。

  • static int mergeSort(int[] a)
    指定された配列を数値の昇順でソート

MergeSortクラスを作成し、以下のメソッドを記述してください。

public class MergeSort {
    public static void mergeSort(int[] a) {
        if (a.length > 1) {
            // 配列の分割
            int a1_len = a.length / 2;
            int a2_len = a.length - a1_len;
            int[] a1 = new int[a1_len];
            int[] a2 = new int[a2_len];
            for (int i = 0; i < a1_len; i++) {
                a1[i] = a[i];
            }
            for (int i = 0; i < a2_len; i++) {
                a2[i] = a[a1_len + i];
            }

            // 配列のソート(マージソートを再帰呼び出し)
            mergeSort(a1);
            mergeSort(a2);

            // 配列のマージ
            merge(a1, a2, a);
        }
    }

    private static void merge(int[] a1, int[] a2, int[] a) {
        // マージする2配列を表示
        System.out.print("a1={");
        for (int k = 0; k < a1.length; k++) {
            System.out.print(a1[k] + ", ");
        }
        System.out.print("}, a2={");
        for (int k = 0; k < a2.length; k++) {
            System.out.print(a2[k] + ", ");
        }
        System.out.print("}");

        int a_i = 0;
        int a1_i = 0;
        int a2_i = 0;
        while (true) {
            // どちらが小さいかを判断し、小さい方をマージ後の配列に追加
            if (a1[a1_i] < a2[a2_i]) {
                a[a_i++] = a1[a1_i++];
            } else {
                a[a_i++] = a2[a2_i++];
            }
            // どちらかの配列が最後まで行ったらループ終了
            if (a1_i == a1.length || a2_i == a2.length) {
                break;
            }
        }
        // 残っている方の配列をマージ後配列に追加(実際にはwhile文はどちらかしか実行されない)
        while (a1_i < a1.length) {
            a[a_i++] = a1[a1_i++];
        }
        while (a2_i < a2.length) {
            a[a_i++] = a2[a2_i++];
        }

        // マージ後の配列を表示
        System.out.print(" => a={");
        for (int k = 0; k < a.length; k++) {
            System.out.print(a[k] + ", ");
        }
        System.out.println("}");
    }
}

mergeSortメソッドでは配列の分割、mergeSortメソッドの再帰呼び出しを行っています。最後にmergeメソッドを呼び出しマージを行っています。

mergeメソッドでは前項で説明した通りに小さい順にマージを行っています。状況表示を行っているため少し長くなっています。

動作確認

動作確認用のクラスを作成し、mainメソッドに以下の内容を記述します。

public static void main(String[] args) {
    int[] array = {11, 3, 28, 14, 23, 7, 4, 1, 5, 20};

    MergeSort.mergeSort(array);
}

動作結果(mergeSortメソッド内部で並び替え状況が出力されています)

a1={11, }, a2={3, } => a={3, 11, }
a1={14, }, a2={23, } => a={14, 23, }
a1={28, }, a2={14, 23, } => a={14, 23, 28, }
a1={3, 11, }, a2={14, 23, 28, } => a={3, 11, 14, 23, 28, }
a1={7, }, a2={4, } => a={4, 7, }
a1={5, }, a2={20, } => a={5, 20, }
a1={1, }, a2={5, 20, } => a={1, 5, 20, }
a1={4, 7, }, a2={1, 5, 20, } => a={1, 4, 5, 7, 20, }
a1={3, 11, 14, 23, 28, }, a2={1, 4, 5, 7, 20, } => a={1, 3, 4, 5, 7, 11, 14, 20, 23, 28, }

配列が分割され、マージされ、マージされた配列がさらにマージされていくことで最終的にソートが行えていることがわかります。

マージソートの解説

コードを読むだけではアルゴリズムの仕組みが分かりにくいので、今回も実際にアルゴリズムを実装する工程を追いかけてみましょう。長いですが、やっていることは簡単なので心配しないでください。クイックソートに引き続き、マージソートでも再帰呼び出しを扱います。

  1. 配列分割用・マージ用、それぞれのメソッドを作成する
  2. 配列を分割する処理を組み立てる
  3. 配列をマージする処理を組み立てる

それでは順番に見ていきましょう。

  1. 配列分割用・マージ用、それぞれのメソッドを作成する

mergeSortメソッドは配列の分割を担当し、Javaのメイン処理から直接呼び出されるメソッドです。mergeメソッドは配列のマージを担当し、mergeSortメソッドから配列の分割が終わった後に呼び出されます。

public static void mergeSort(int[] a) {
}

private static void merge(int[] a1, int[] a2, int[] a) {
}
  1. 配列を分割する処理を組み立てる

配列を分割する処理を追記します。新しく2つの配列(a1, a2)を用意し、対象配列を半分に分割してそれぞれの配列に格納します。その後、mergeSort(a1)mergeSort(a2)で、2つの再帰呼び出し処理を行うことで、二分木を形成します。これにより、配列が最小まで分割されたところで、if文のa.length > 1の条件によって再帰から抜け出します。

この後、分割した配列をマージするのでmerge(a1, a2, a)を記述しています。ここでは二分木のリーフノード(末端)からマージされていきます。

少し補足すると、最初にmergeSort(a1)によって、何度も再帰呼び出しが行われ、二分木の左ノードを辿りながら一番下のリーフノードに移動します。if (a.length > 1)で再帰を抜けると一つ上のノードに移動します。続いて、mergeSort(a2)によって一度、右ノードに移動します。再度、if (a.length > 1)で再帰を抜けた後に、merge(a1, a2, a)に入ります。つまり、ルートノードから見て左ノードを辿った先のリーフノードのa1, a2が一番最初のマージ対象になります。

public static void mergeSort(int[] a) {
    if (a.length > 1) {
        // 配列の分割
        int a1_len = a.length / 2;
        int a2_len = a.length - a1_len;
        int[] a1 = new int[a1_len];
        int[] a2 = new int[a2_len];
        for (int i = 0; i < a1_len; i++) {
            a1[i] = a[i];
        }
        for (int i = 0; i < a2_len; i++) {
            a2[i] = a[a1_len + i];
        }

        // 配列のソート(マージソートを再帰呼び出し)
        mergeSort(a1);
        mergeSort(a2);
        
        // 配列のマージ
        merge(a1, a2, a);
    }
}

private static void merge(int[] a1, int[] a2, int[] a) {
}
  1. 配列をマージする処理を組み立てる

配列をマージする処理を追記します。while文の中のif文によってa1a2を比較しながら小さい順に配列aにマージを行います。a[a_i++] = a1[a1_i++]という書き方に違和感があるかもしれませんが、これはa[a_i] = a1[a1_i]を行った後にa_i++a1_i++を行うことと同じと考えて問題ありません。a1a2のどちらかの配列のマージが終わったらwhile文から抜けます。
最後にwhile文でa1a2の残ったほうの配列を配列aにマージします。どちらかの配列のマージが完了した時点で残りの配列(a1、またはa2)をそのままマージすることで昇順になります。

public static void mergeSort(int[] a) {
    if (a.length > 1) {
        // 配列の分割
        int a1_len = a.length / 2;
        int a2_len = a.length - a1_len;
        int[] a1 = new int[a1_len];
        int[] a2 = new int[a2_len];
        for (int i = 0; i < a1_len; i++) {
            a1[i] = a[i];
        }
        for (int i = 0; i < a2_len; i++) {
            a2[i] = a[a1_len + i];
        }

        // 配列のソート(マージソートを再帰呼び出し)
        mergeSort(a1);
        mergeSort(a2);
        
        // 配列のマージ
        merge(a1, a2, a);
    }
}

private static void merge(int[] a1, int[] a2, int[] a) {
    int a_i = 0;
    int a1_i = 0;
    int a2_i = 0;
    while (true) {
        // どちらが小さいかを判断し、小さい方をマージ後の配列に追加
        if (a1[a1_i] < a2[a2_i]) {
            a[a_i++] = a1[a1_i++];
        } else {
            a[a_i++] = a2[a2_i++];
        }
        // どちらかの配列が最後まで行ったらループ終了
        if (a1_i == a1.length || a2_i == a2.length) {
            break;
        }
    }
    // 残っている方の配列をマージ後配列に追加(実際にはwhile文はどちらかしか実行されない)
    while (a1_i < a1.length) {
        a[a_i++] = a1[a1_i++];
    }
    while (a2_i < a2.length) {
        a[a_i++] = a2[a2_i++];
    }
}

これでマージソートが完成しました。

マージソートの計算量

マージソートの計算量を考えます。マージソートは配列を半分ずつにしていきソートを行います。半分ずつにしていくので再帰呼び出しの回数は$log_2n$回になります。この際、必ず配列を半分にするのでクイックソートのように最悪だと$n$回のように多くなることはありません。

分割した配列をマージする際には比較を行う必要があります。これには配列の大きさ分の回数が必要になります。結局、マージソートの計算量は$O(nlog_2n)$になります。

さて、マージソートの計算量は$O(nlog_2n)$ですが、クイックソートと比較するとどちらが速いでしょうか。一般的にはクイックソートの方が速くなります。マージソートを使うメリットは最悪の場合でも計算量が$O(nlog_2n)$であるという点です。

これまでは計算量として主に時間について考えてきました。今回は空間についても考えてみましょう。空間とは具体的には、そのソートを行うのに必要なメモリ量のことです。

クイックソートでは渡された配列(メモリ領域)に対して直接入れ替え処理を行っています。そのため、クイックソートでは空間計算量はそれほど必要ありません。

一方、マージソートでは渡された配列に対して部分配列をnewで作成していました。今回は簡単にするために毎回newを行っており、かなりのメモリが必要になっています。アルゴリズムを工夫することによりメモリ量を減らすことはできますが通常、ソート対象の配列と同じ大きさの作業領域が必要になります。

このように、マージソートは最悪実行時間という点ではクイックソートに勝っているが、平均実行時間、また、使用メモリという点では負けているということになります。アルゴリズムを選択する際には平均実行時間、最悪実行時間、使用メモリなど様々な要素を考慮し、どのアルゴリズムを利用するか決定する必要があります。

参考資料
スクールの教科書
計算機プログラムの構造と解釈 第二版