JavaScript におけるマージソート

JavaScriptJavaScriptBeginner
今すぐ練習

This tutorial is from open-source community. Access the source code

💡 このチュートリアルは英語版からAIによって翻訳されています。原文を確認するには、 ここをクリックしてください

はじめに

この実験では、JavaScript でマージソートアルゴリズムを調べます。マージソートは、分割統治法の人気のあるソートアルゴリズムで、効率的で実際によく使われています。この実験が終わるとき、マージソートがどのように機能するか、および独自の JavaScript プロジェクトでそれを実装する方法をしっかりと理解しているでしょう。


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL javascript(("JavaScript")) -.-> javascript/BasicConceptsGroup(["Basic Concepts"]) javascript/BasicConceptsGroup -.-> javascript/variables("Variables") javascript/BasicConceptsGroup -.-> javascript/data_types("Data Types") javascript/BasicConceptsGroup -.-> javascript/arith_ops("Arithmetic Operators") javascript/BasicConceptsGroup -.-> javascript/comp_ops("Comparison Operators") javascript/BasicConceptsGroup -.-> javascript/cond_stmts("Conditional Statements") javascript/BasicConceptsGroup -.-> javascript/array_methods("Array Methods") subgraph Lab Skills javascript/variables -.-> lab-28496{{"JavaScript におけるマージソート"}} javascript/data_types -.-> lab-28496{{"JavaScript におけるマージソート"}} javascript/arith_ops -.-> lab-28496{{"JavaScript におけるマージソート"}} javascript/comp_ops -.-> lab-28496{{"JavaScript におけるマージソート"}} javascript/cond_stmts -.-> lab-28496{{"JavaScript におけるマージソート"}} javascript/array_methods -.-> lab-28496{{"JavaScript におけるマージソート"}} end

マージソートアルゴリズム

マージソートアルゴリズムを使ったコーディングを練習するには、次の手順に従います。

  1. ターミナル/SSH を開き、node と入力します。
  2. 再帰を使って数字の配列をソートします。
  3. 配列の length2 未満の場合、配列を返します。
  4. Math.floor() を使って配列の中央点を計算します。
  5. Array.prototype.slice() を使って配列を 2 つに分割し、生成されたサブ配列に対して再帰的に mergeSort() を呼び出します。
  6. 最後に、Array.from()Array.prototype.shift() を使って 2 つのソート済みサブ配列を 1 つに結合します。

以下がコードです。

const mergeSort = (arr) => {
  if (arr.length < 2) return arr;
  const mid = Math.floor(arr.length / 2);
  const l = mergeSort(arr.slice(0, mid));
  const r = mergeSort(arr.slice(mid, arr.length));
  return Array.from({ length: l.length + r.length }, () => {
    if (!l.length) return r.shift();
    else if (!r.length) return l.shift();
    else return l[0] > r[0] ? r.shift() : l.shift();
  });
};

この例で試してみましょう。

mergeSort([5, 1, 4, 2, 3]); // [1, 2, 3, 4, 5]

まとめ

おめでとうございます!あなたはマージソートの実験を完了しました。あなたの技術を向上させるために、LabEx でさらに多くの実験を練習することができます。