JavaScript
 Computer >> コンピューター >  >> プログラミング >> JavaScript

JavaScriptでマージソートを実装する方法をわかりやすく解説

マージソートとは

マージソートは「分割統治法（Divide and Conquer）」に基づく代表的なソートアルゴリズムの一つです。入力として与えられた配列の要素を、小さい順（昇順）に並べ替えることを目的としています。

大きな問題（配列全体の並べ替え）を小さな問題（要素が1つの配列）に分割し、それらを順番に統合しながら解いていくのが特徴です。計算量は平均・最悪ともに O(n log n) と効率的で、安定したソートが必要な場面でよく使われます。

マージソートの手順

  • 分割： まず配列を2つの部分配列に分け、さらにそれぞれを2つずつに分割していき、要素が1つだけの配列だらけになるまで繰り返します。たとえば、[4,7,5,9,1,3,8,2] という配列は、[4]、[7]、[5]、[9]、[1]、[3]、[8]、[2] という要素1つの配列に分割されます。
  • 統合（1回目）： 次に、2つの配列ずつ値を比較しながら結合していきます。[4] と [7] を比較・結合して [4,7] を作り、同様に [5] と [9]、[1] と [3]、[8] と [2] を結合して、[4,7]、[5,9]、[1,3]、[2,8] の4つの配列が形成されます。
  • 統合（2回目）： 同じ要領で、2つの配列ずつ比較と結合を続けます。[4,7] と [5,9] を比較・結合すると [4,5,7,9] になり、残りの2つも同様に結合して [1,2,3,8] ができます。
  • 統合（最終）： 最後に残った2つの配列を比較・結合すれば、[1,2,3,4,5,7,8,9] というソート済みの最終配列が完成します。

コード例

以下は、再帰処理を使ってマージソートをJavaScriptで実装したサンプルです。mSort関数が配列の分割を担当し、merge関数が比較と統合を担当します。

<html>
<body>
<script>
    function mSort(array) {
        if (array.length === 1) {
            return array;                  // 要素が1つだけになったらそのまま返す
        }
        const middle = Math.floor(array.length / 2); // 配列の中央位置（小数点以下切り捨て）
        const left = array.slice(0, middle);         // 左半分の要素
        const right = array.slice(middle);           // 右半分の要素
        document.write(middle);
        return merge(
            mSort(left),
            mSort(right)
        )
    }
    // 配列同士を1項目ずつ比較し、結合した結果を返す
    function merge(left, right) {
        let result = []
        let leftIndex = 0
        let rightIndex = 0
        while (leftIndex < left.length && rightIndex < right.length) {
            if (left[leftIndex] < right[rightIndex]) {
                result.push(left[leftIndex])
                leftIndex++
                document.write("</br>");
            } else {
                result.push(right[rightIndex])
                rightIndex++
            }
        }
        return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
    }
    const list = [4,7,5,9,1,3,8,2]
    document.write(mSort(list));
</script>
</body>
</html>

実行結果

1,2,3,4,5,7,8,9

このように、バラバラだった要素が正しく昇順に並べ替えられて出力されます。実務では document.write による出力は推奨されないため、console.log などを使うとより良いでしょう。


  1. JavaScriptのArray.prototype.sort()メソッドの使い方をサンプルコードで解説

    Array.prototype.sort()は、JavaScriptで配列の要素を並べ替えるための組み込みメソッドです。アルファベット順・数値順といった並び方に加えて、昇順・降順も自由に指定でき、配列操作の中でも特に使用頻度の高いメソッドの一つです。 ただし重要なポイントとして、sort()メソッドはデフォルトではすべての要素を文字列に変換してから比較します。そのため、数値の配列を意図したとおりに並べ替えたい場合は、比較関数を引数として渡す必要があります。 以下は、Array.prototype.sort()メソッドの基本的な使い方を示すサンプルコードです。 サンプルコード <!DOC

  2. JavaScriptで配列をreduceする方法｜reduce()メソッドで配列要素を合計する

    JavaScriptのreduce()メソッドは、配列の各要素を先頭から順に処理し、その結果を1つの値にまとめる（畳み込む）ための配列メソッドです。数値の合計を求めるだけでなく、配列からオブジェクトを組み立てたり、条件に応じてデータを集約したりと、幅広い場面で活用されています。reduce()メソッドの基本構文 { return 戻り値; }, 初期値);accumulator（アキュムレータ）：直前のコールバック関数が返した値（累積値）。最初のループでは初期値、または配列の第1要素が代入されます。currentValue：現在処理している配列の要素。初期値：累積値の出発点となる値。省略し