JavaScriptアルゴリズム:クイックソート

クイックソートは、より効率的な検索アルゴリズムです。選択ソートほとんどの場合、そしてそれは再帰を利用します。

再帰とは、同じ関数内から関数を呼び出すことを意味します。これは非常に便利な方法である場合があり、これはそのようなケースの1つです。

「ほとんどの場合」と言いました。これから説明するように、最悪の場合、バブルソートは選択ソートと同じ時間を要する可能性があるためです。O(n^2)。しかし、最良のシナリオでは、次の場所で実行されます。O(n log n)、の中間にありますO(n)そしてO(n^2)

それはどのように機能しますか?配列が与えられると、と呼ばれるアイテムを選択しますピボット。次に、すべてのアイテムをピボットより小さくし、アイテムをピボットより大きくします。

次に、小さいアイテムと大きいアイテムを構成する2つの配列に対して同じ操作を実行します。

コードを説明するよりも、コードを見る方が簡単です。

const quickSort = (originalList) => {
  const list = [...originalList]

if (list.length < 2) { return list }

const pivot = list[0]

const smaller = list.filter((item) => item < pivot) const bigger = list.filter((item) => item > pivot)

return […quickSort(smaller), pivot, …quickSort(bigger)] }

この場合、配列の最初のアイテムとしてピボットを選択しましたが、たとえば、中央のアイテムにすることもできます。

const pivot = list[Math(floor(list.length / 2)]

最初に配列をコピーする方法に注目してください。quickSort()元の配列を変更せず、新しい並べ替えられた配列を返すだけです。

const a = [1, 6, 3, 4, 5, 1, 0, 4, 8]

console.log(quickSort(a)) //[0, 1, 1, 3, 4, 4, 5, 6, 8 console.log(a) //[1, 6, 3, 4, 5, 1, 0, 4, 8]

私の無料ダウンロードJavaScriptビギナーズハンドブック


その他のjsチュートリアル: