🎯

【Java】マージソート

2024/03/18に公開

Java

初心者

tech

マージソートとは

分割・再帰・結合という３ステップを踏む効率的なアルゴリズムの一つです。
分割により、配列を２つに分割して部分配列を作成します。
再帰により、その部分配列を再帰的に分割して、要素が１つになるまで繰り返します。
結合により、部分配列の先頭を比較しながらソートを行い、部分配列を結合していき、最終的にソートされた配列を作成します。

問題の内容

問題
サイズnの数列aをマージソートせよ。
入力値
```
n = 4
a = 4 2 8 1
```

マージソートの図解

マージソートを図解すると、下記の通りになります。

本問のマージソートの解説

本問では再帰処理を使いますので、解説を先に行います。
再帰処理は、途中経過がブラックボックスであり、従前に解説したシェルソートのように制御変数の変化を考えて処理の流れを直接追うことが難しいためです。
詳しくは、下記の記事を参考にしてください。

私が理解に躓いてしまった箇所のみを解説します。

1.表題の考え方について

「マージソートの図解」では、分割とマージが出てきました。
「コード例」では、mergeSortメソッドとmergeメソッドが出てきます。
分割に当たる部分はmergeSortメソッドであり、マージに当たる部分はmergeメソッドです。

2.再帰処理の終了条件

mergeSortメソッドでは、再帰処理を行うため、再帰処理の終了条件を下記の通りに設定します。

if (left >= right - 1) {
    return;
}

具体的に言えば、left=0でright=1の時は、その部分配列の要素数が1となり、そして、再帰処理の終了条件を満たします。

3.番兵である変数INFを定義する理由

例として、図解の4と2マージする場面を挙げます。
この時、mergeメソッドの配列lとrは、下記の通りです。

l = [4, 10億1]
r = [2, 10億1]

両配列の先頭の要素l[0]とr[0]を比較して
より小さいr[0]の2を配列aに代入します。
rのインデックスを1進めます。
次のループで両配列の先頭の要素l[0]とr[1]を比較します。
!

この時、番兵が配列rに入っていないと、配列外のインデックスにアクセスしようとしてエラーになってしまいます。
また、上記のエラーを避けるために配列の境界チェックやif文で条件分岐等を行う必要があります。
したがって、上記のエラーを避けつつ、コードを簡略化するために番兵を用意します。

本問のマージソートのコード例

import java.util.*;

public class Main {
    // 番兵である変数INFを10億1で定義
    static final int INF = 1000000001;
    static int count = 0;

    // マージ
    static void merge(int[] a, int left, int mid, int right) {
        // 左側の配列の要素数を定義
        int nl = mid - left;
        // 右側の配列の要素数を定義
        int nr = right - mid;

        // 分割した左側の配列をコピーする配列を定義（サイズの +1 は番兵を追加するため）
        int[] l = new int[nl + 1];
        // 分割した右側の配列をコピーする配列を定義（サイズの +1 は番兵を追加するため）
        int[] r = new int[nr + 1];

        // 元の配列aの左側の配列に当たる要素をコピー配列lに代入
        for (int i = 0; i < nl; i++) {
            l[i] = a[left + i];
        }
        // 元の配列aの右側の配列に当たる要素をコピー配列rに代入
        for (int i = 0; i < nr; i++) {
            r[i] = a[mid + i];
        }

        // コピー配列lの末尾に番兵を追加
        l[nl] = INF;
        // コピー配列rの末尾に番兵を追加
        r[nr] = INF;

        // コピー配列lのインデックスである変数lIndexを0で初期化
        int lIndex = 0;
        // コピー配列rのインデックスである変数rIndexを0で初期化
        int rIndex = 0;

        // コピー配列lとコピー配列rの先頭の要素を比較して小さい値を元の配列aに代入する
        for (int i = left; i < right; i++) {
            // l と r の先頭の要素のうち l の先頭要素が小さいなら
            if (l[lIndex] < r[rIndex]) {
                // l の先頭の要素を元の配列aに代入
                a[i] = l[lIndex];
                // l の先頭のインデックスを 1 つ進める
                lIndex++;
            // l と r の先頭の要素のうち r の先頭要素が小さいなら
            } else {
                // r の先頭の要素を元の配列aに格納
                a[i] = r[rIndex];
                // r の先頭のインデックスを 1 つ進める
                rIndex++;
                count++;
            }
        }
    }
    // マージソート（再帰処理）
    static void mergeSort(int[] a, int left, int right) {
        // 再帰処理の終了条件を配列の先頭のインデックス=left が配列の末尾のインデックス=right-1 以上に設定
        // →分割した配列の要素数が1個以下になるまで再帰処理を繰り返す
        if (left >= right - 1) {
            return;
        }
        // 配列を2分割するための中間のインデックスである変数midを定義（切り捨てとします。）
        int mid = (left + right) / 2;
        // 左側の配列に再帰処理を行い要素数が1個以下になるまで分割
        mergeSort(a, left, mid);
        // 右側の配列に再帰処理を行い要素数が1個以下になるまで分割
        mergeSort(a, mid, right);
        // mergeを呼び出す
        merge(a, left, mid, right);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        mergeSort(a, 0, n);

        for (int i = 0; i < n; i++) {
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(a[i]);
        }
        System.out.println();

        System.out.println(count);
    }
}