Javaでのマージソート

投稿日: 2019-10-19 2022-11-03
タグ: Algorithms, Java

1. 序章

このチュートリアルでは、マージソートアルゴリズムとそのJavaでの実装について説明します。

マージソートは最も効率的なソート手法の1つであり、「分割統治」パラダイムに基づいています。

2. アルゴリズム

マージソートは「分割統治」アルゴリズムであり、最初に問題をサブ問題に分割します。サブ問題の解決策の準備ができたら、それらを組み合わせて問題の最終的な解決策を取得します。

メインの問題ではなくサブの問題を処理するため、再帰を使用してこのアルゴリズムを簡単に実装できます。

アルゴリズムは、次の2ステップのプロセスとして説明できます。

除算：このステップでは、入力配列を2つに分割します。ピボットは配列の中点です。このステップは、分割するハーフアレイがなくなるまで、すべてのハーフアレイに対して再帰的に実行されます。
征服：このステップでは、分割された配列を下から上に並べ替えてマージし、並べ替えられた配列を取得します。

次の図は、配列{10、6、8、5、7、3、4}の例の完全なマージソートプロセスを示しています。

図を詳しく見ると、サイズが1になるまで、配列が再帰的に2つに分割されていることがわかります。サイズが1になると、マージプロセスが実行され、並べ替え中に配列のマージが開始されます。

3. 実装

実装では、入力配列とその長さをパラメーターとして受け取るmergeSort関数を記述します。これは再帰関数になるので、基本条件と再帰条件が必要です。

基本条件は、配列の長さが1であるかどうかをチェックし、それが返されるだけです。残りのケースでは、再帰呼び出しが実行されます。

再帰的な場合、中央のインデックスを取得し、l[]とr[]の2つの一時配列を作成します。次に、両方のサブ配列に対してmergeSort関数を再帰的に呼び出します。

public static void mergeSort(int[] a, int n) {
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int[] l = new int[mid];
    int[] r = new int[n - mid];

    for (int i = 0; i < mid; i++) {
        l[i] = a[i];
    }
    for (int i = mid; i < n; i++) {
        r[i - mid] = a[i];
    }
    mergeSort(l, mid);
    mergeSort(r, n - mid);

    merge(a, l, r, mid, n - mid);
}

次に、入力と両方のサブ配列、および両方のサブ配列の開始インデックスと終了インデックスを取り込むマージ関数を呼び出します。

merge 関数は、両方のサブ配列の要素を1つずつ比較し、小さい方の要素を入力配列に配置します。

サブ配列の1つが終了すると、他の配列の残りの要素が入力配列にコピーされ、最終的にソートされた配列が得られます。

public static void merge(
  int[] a, int[] l, int[] r, int left, int right) {
 
    int i = 0, j = 0, k = 0;
    while (i < left && j < right) {
        if (l[i] <= r[j]) {
            a[k++] = l[i++];
        }
        else {
            a[k++] = r[j++];
        }
    }
    while (i < left) {
        a[k++] = l[i++];
    }
    while (j < right) {
        a[k++] = r[j++];
    }
}

プログラムの単体テストは次のとおりです。

@Test
public void positiveTest() {
    int[] actual = { 5, 1, 6, 2, 3, 4 };
    int[] expected = { 1, 2, 3, 4, 5, 6 };
    MergeSort.mergeSort(actual, actual.length);
    assertArrayEquals(expected, actual);
}

4. 複雑

マージソートは再帰的アルゴリズムであるため、時間計算量は次の再帰的関係として表すことができます。

T(n) = 2T(n/2) + O(n)

2T（n / 2）はサブ配列のソートに必要な時間に対応し、 O（n）は配列全体をマージする時間です。

解決すると、時間計算量はO（nLogn）になります。

これは、最悪の場合、平均的な場合、および最良の場合に当てはまります。これは、配列が常に2つに分割されてから、マージされるためです。

再帰呼び出しごとに一時配列を作成しているため、アルゴリズムのスペースの複雑さは O（n）、です。

5. 結論

この短い記事では、マージソートアルゴリズムと、それをJavaで実装する方法について説明しました。

動作するコード全体は、GitHubでから入手できます。

getdocs

13036