Javascriptでのマージソートとクイックソート

---

マージソートは、分割統治法に基づくソート手法です。最悪の場合の時間計算量はΟ（n log n）です。ただし、このアルゴリズムは余分なO（n）メモリを必要とするため、スペースの面で追加のコストが発生します。

次に、このアルゴリズムをどのように実装するかを見てみましょう。 mergeSortとmergeの2つの関数を作成します。

マージ −この関数は2つの引数を取ります。これらは、2つの部分配列であり、要素を正しい順序で挿入することにより、1つに連結されます。

マージソート −この関数は、配列の左半分と右半分でmergeSortを再帰的に呼び出し、mergeを使用してこれらの配列部分を結合します。実装を見ると、これははるかに明確になります。

マージ関数から始めて、すぐにコードに飛び込みましょう-

例

function merge(left, right) {
   let mergedArr = [];
   let i = 0;
   let j = 0;
   // Try merging till we reach end of either one of the arrays.
   while (i < left.length && j < right.length) {
      if (compare(left[i], right[j])) {
         mergedArr.push(left[i]);
         i++;
      } else {
         mergedArr.push(right[j]);
         j++;
      }
   }
   // If left was 1, 2, 3, 5 and right was 4, 6, 7, 9
   // the for loop above would stop once it reaches the end of
   // The left array leaving 3 elements in the right array
   // In order to add the remaining elements from either array,
   // We need to add elements from i to end in left and j to end
   // in the right array to the merged array.
   return mergedArr.concat(left.slice(i)).concat(right.slice(j));
}

この関数は、2つのソートされた配列を受け取り、それらをO（n）時間でマージして、より大きな配列としてソートされたままにするようにします。メソッドの詳細な説明については、コードコメントを参照してください。これは、-

を使用してテストできます。

例

let a1 = [1, 2, 3, 5]
let a2 = [4, 6, 8, 9]
console.log(merge(a1, a2))

出力

[1, 2, 3, 4, 5, 8, 9]

次に、この関数をマージソート関数で使用して、実際に配列全体をソートします。

mergeSortの内部関数を作成します。これを外部関数でラップして、コンパレーターを使用可能にし、関数を拡張できるようにします。この内部関数を見てみましょう-

例

function mergeSortInner(arr) {
   if (arr.length < 2) {
      return arr;
   }
   let mid = Math.floor(arr.length / 2);
   // Create an array from 0 to mid - 1 elements
   let left = arr.slice(0, mid);
   // Create an array from mid to the last element
   let right = arr.slice(mid);
   // Sort the left half, sort the right half,
   // merge the sorted arrays and return
   return merge(mergeSortInner(left), mergeSortInner(right));
}

この関数は、配列を取得して2つに分割し、それらを個別に並べ替えてから、マージされた配列を返します。

テストで完全なコードを見てみましょう-

例

function mergeSort(arr, compare = (a, b) => a < b) {
   function merge(left, right) {
      let mergedArr = [];
      let i = 0;
      let j = 0;
      // Try merging till we reach end of either one of the arrays.
      while (i < left.length && j < right.length) {
         if (compare(left[i], right[j])) {
            mergedArr.push(left[i]);
            i++;
         } else {
            mergedArr.push(right[j]);
            j++;
         }
      }
      // If left was 1, 2, 3, 5 and right was 4, 6, 7, 9
      // the for loop above would stop once it reaches the end of
      // The left array leaving 3 elements in the right array
      // In order to add the remaining elements from either array,
      // We need to add elements from i to end in left and j to end
      // in the right array to the merged array.
      return mergedArr.concat(left.slice(i)).concat(right.slice(j));
   }
   function mergeSortInner(arr) {
      if (arr.length < 2) {
         return arr;
      }
      let mid = Math.floor(arr.length / 2);
      let left = arr.slice(0, mid);
      let right = arr.slice(mid);
      return merge(mergeSortInner(left), mergeSortInner(right));
   }
   // Call inner mergesort to sort and return the array for us.
   return mergeSortInner(arr);
}
You can test this using:
let arr = [5, 8, 9, 12, -8, 31, 2];
// Sort Array elements in increasing order
arr = mergeSort(arr);
console.log(arr);
// Sort Array elements in decreasing order
arr = mergeSort(arr, (a, b) => a > b);
console.log(arr);
arr = [
   {
      name: "Harry",
      age: 20
   },
   {
      name: "Jacob",
      age: 25
   },
   {
      name: "Mary",
      age: 12
   }
];
// Sort Array elements in increasing order alphabetically by names
arr = mergeSort(arr, (a, b) => a.name < b.name);
console.log(arr);
// Sort Array elements in decreasing order of ages
arr = mergeSort(arr, (a, b) => a.age < b.age);
console.log(arr);

出力

[ -8, 2, 5, 8, 9, 12, 31 ]
[ 31, 12, 9, 8, 5, 2, -8 ]
[
   { name: 'Harry', age: 20 },
   { name: 'Jacob', age: 25 },
   { name: 'Mary', age: 12 }
]
[
   { name: 'Mary', age: 12 },
   { name: 'Harry', age: 20 },
   { name: 'Jacob', age: 25 }
]

クイックソート

クイックソートは非常に効率的なソートアルゴリズムであり、データの配列をより小さな配列に分割することに基づいています。大きな配列は2つの配列に分割され、そのうちの1つは指定された値よりも小さい値、たとえばピボットを保持します。これに基づいて分割が行われ、もう1つの配列はピボット値よりも大きい値を保持します。

クイックソートは配列を分割し、それ自体を再帰的に2回呼び出して、結果の2つのサブ配列をソートします。このアルゴリズムは、平均および最悪の場合の複雑さがΟ（n2）であるため、大規模なデータセットに対して非常に効率的です。ここで、nはアイテムの数です。

パーティションプロセス

次のアニメーション表現は、配列内のピボット値を見つける方法を説明しています。https：//www.tutorialspoint.com/data_structures_algorithms/images/quick_sort_partition_animation.gif

ピボット値は、リストを2つの部分に分割します。そして再帰的に、すべてのリストに1つの要素のみが含まれるまで、各サブリストのピボットを見つけます。

パーティショニングで行うことは、配列から最初の要素（ランダム化されたクイックソートのランダムな要素）を選択し、配列の残りの部分をこの要素と比較することです。次に、この要素よりも小さいすべての要素をピボットインデックスと呼ばれるものの左側に移動し、これよりも大きい値をピボットインデックスの右側に移動します。したがって、最後に到達すると、ピボット要素（最初の要素）が正しい位置に配置されます。

これは、すべての要素が右側にあり、左側にあるため、この要素が正しい場所にあるためです。このパーティション化プロセスを拡張して、左右のサブ配列でパーティションを再帰的に呼び出すことで並べ替えを支援します。

パーティション関数は次のように実装できます-

例

function partition(arr, low, high, compare) {
   let pivotIndex = low + 1;
   for (let i = pivotIndex; i < high; i++) {
      if (compare(arr[i], arr[low])) {
      // Swap the number less than the pivot
      swap(arr, i, pivotIndex);
      pivotIndex += 1;
      }
   }
   // Place the pivot to its correct position
   swap(arr, pivotIndex - 1, low);
   // Return pivot's position
   return pivotIndex - 1;
}
function swap(arr, i, j) {
   let temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
}
You can test the partition function using:
let arr = [5, 1, 10, 8, 9, 3, 2, 45, -6];
console.log(partition(arr, 0, arr.length, (l, r) => l < r));
console.log(arr);

出力

4
[ -6, 1, 3, 2, 5, 10, 8, 45, 9 ]

5の左側の要素は5未満であり、右側の要素は5より大きいことに注意してください。また、5のインデックスは4であることがわかります。

次に、クイックソートがどのように機能するかを見てみましょう-

1要素より大きいウィンドウがある場合は、配列のパーティションを低いものから高いものへと呼び出し、返されたインデックスを取得し、それを使用して配列の左半分と右半分でクイックソートを呼び出します。

例

function QuickSort(arr, low, high, compare = (l, r) => l < r) {
   if (high - low > 0) {
      // Partition the array
      let mid = partition(arr, low, high, compare);
      // Recursively sort the left half
      QuickSort(arr, low, mid, compare);
      // Recursively sort the right half
      QuickSort(arr, mid + 1, high, compare);
   }
}
You can test this using:
let arr = [5, 1, 10, 8, 9, 3, 2, 45, -6];
QuickSort(arr, 0, arr.length, (l, r) => l < r);
console.log(arr);

出力

[ -6, 1, 2, 3, 5, 8, 9, 10, 45 ]