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

JavaScriptでマージソートを実装する方法は？

マージソート

マージソートは、分割統治タイプのソートアルゴリズムの例です。マージソートの入力は、いくつかの要素の配列であり、通常、最小から最大に配置する必要があります。

マージソートで従う手順

  • マージソートは、配列を2つのサブ配列に分割し、後で各配列を別の2つの配列に分割し、以下同様に、多数の単一要素配列が残るまで続けます。たとえば、次の例では、配列[4,7,5,9,1,3,8,2]は、[4]、[7]、[5]、[9]などの単一の配列要素に分割されます。 [1]、[3]、[8]、[2]。
  • 2つのアレイが比較され、連結されるように、アレイの比較が開始されます。次の例では、一度に2つの配列を比較します。つまり、[4]、[7]を比較して連結し、次に[5]、[9]を比較して連結し、以下同様に配列[4,7]、[ 5,9]、[1,3]、[2,8]が形成されます。
  • 2つの配列を比較して連結し、2つの配列を形成するのと同じ方法に従います。次の例では、[4,7]と[5,9]を比較して連結し、[4,5,7,9]として配列を取得します。他の2つの配列の場合も同様で、[1、 2,3,8]。
  • ここで適用できる同じルールは、残りの2つの配列を比較して連結し、[1,2,3,4,5,7,8,9]として最終的な配列を取得します。

例

<html>
<body>
<script>
   function mSort (array) {
      if (array.length === 1) {
      return array                            // return once we hit an array with a single item
   }
   const middle = Math.floor(array.length / 2) // get the middle item of the array rounded down
   const left = array.slice(0, middle)         // items on the left side
   const right = array.slice(middle)           // items on the right side
   document.write(middle);
   return merge(
      mSort(left),
      mSort(right)
   )
   }
   // compare the arrays item by item and return the concatenated result
   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

  1. JavaScriptのArray.prototype.sort（）。

    JavaScript Array.prototype.sort（）メソッドは、配列の並べ替えに使用されます。並べ替えの順序は、アルファベット、数字、昇順、降順のいずれかです。 以下は、Array.prototype.sort（）メソッドのコードです- 例 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8" /> <meta name="viewport" content="width=device-

  2. JavaScriptで配列を減らす方法は？

    以下は、JavaScriptで配列を減らすためのコードです- 例 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8" /> <meta name="viewport" content="width=device-width, initial-scale=1.0" /> <title>Document</title> <style>   &n