JavaScriptによるクイックソートを理解する

投稿日: 2022-04-20 2022-10-06
タグ: javascript

マージソートを使用する際の問題の1つは、ほとんどが冗長データを含む非常に多くの配列を作成してメモリに格納する必要があることです。メモリが制限されている場合は、クイックソートを使用して「インプレース」で実行できます。つまり、変更と結果はすべて、ソートされているものに直接反映されるため、メモリを節約できます。

前提条件

これは繰り返し実行できますが、標準の再帰バージョンについて説明します。再帰がどのように機能するかを理解しておくと、ここでをブラッシュアップできます。

コンセプト

クイックソートは間違いなく直感的でないアルゴリズムの1つなので、ここに非常に簡単な概要を示します。

私たちは私たちと呼ばれる番号を選択します pivot、アイテムをループするときにすべての数値を比較します。目標は、アレイを再編成して2つに分割し、それぞれのすべてがピボットよりも小さいか大きいようにすることです。ピボットが最終位置にあるとき、新しいピボットで同じことを行うことに移ります。すべてのアイテムが少なくとも1回ピボットになるまで、すべてのピボットが所定の位置に固定されます。

VisuAlgo.netのおかげでグラフィック/アニメーション

マージソートと同様に、複雑さは平均してO（nlogn）であるため、どちらを選択するかはあなた次第です。

練習データ

いつものように、これは50個のランダムな数字のソートされていない配列です。また、JavaScriptのパフォーマンスAPI を調べて、他のアルゴリズムやさまざまなデータと比較することをお勧めします。

const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];

ピボット

まず、ピボットユーティリティ関数が必要です。これには、スワッパー、ループ、ピボット自体、およびポインターの4つの主要部分があります。

ポインタは、ピボットの単なるプレースホルダーです。ループが進行するたびに、各アイテムがピボットと比較され、小さい場合はポインターと交換されます。これを行うたびに、ポインターがピボットよりも小さいものすべての前にあり、大きいものすべての前にあることを確認します。すべてが完了し、配列がパーティション化されたら、ピボットをポインタのインデックスに最終位置として割り当てることができます。

私たちのスワップは、各アイテムのインデックスを互いのインデックスに再割り当てするだけで機能します。

const pivot = (arr, start = 0, end = arr.length + 1) => {
  const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]];

  let pivot = arr[start],
      pointer = start;

  for (let i = start; i < arr.length; i++) {
    if (arr[i] < pivot  ) {
      pointer++;
      swap(arr, pointer, i);
    }
  };
  swap(arr, start, pointer);

  return pointer;
}

クイックソート

再帰が発生する傾向があるため、実装は同時に非常に単純で少し混乱します。私たちは私たちを使用するつもりです pivot 配列から最初にソートされたアイテムを取得する関数。それで、再帰的に実行します quickSort パーティション化された配列の前半で同じプロセスを実行します。これは、ソートするものがなくなるまで繰り返され、残りの半分でも同じように実行されます。両方が完了すると、完全にソートされた配列を返すことができます。

const quickSort = (arr, start = 0, end = arr.length) => {
  let pivotIndex = pivot(arr, start, end);

  if (start >= end) return arr;
  quickSort(arr, start, pivotIndex);
  quickSort(arr, pivotIndex + 1, end);

  return arr;
};

console.log(quickSort(unsortedArr));

結論

クイックソートは間違いなく私の頭を包むのに最も難しいソートアルゴリズムの1つでした。 4つの変更パーツと2つの再帰スタックの間に、これは間違いなく完全に覚えておくべきではないものであり、後で参照するためにブックマークすることをお勧めします。

getdocs

13036