[アルゴリズム]クイックソート

クイックソートとは?

クイックソートは、データム点を取得した後、そのデータム点に基づいてソートされます.1つの位置は基準点より小さい項目であり、もう1つの位置は基準点より大きい項目である.分割されたサブアレイに対して、すべてのアレイがデフォルトのアレイ(要素が1つしかないアレイ)になるまで、高速ソートが再帰的に呼び出されます.
数字の基準点を決定する別の方法はありますか?
👉 通常、ソートする配列の最初の要素、最後の要素、およびインデックスを中心値とする要素を基点とします.

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

分割スリット征服スリット結合

パーティション
ソートする配列を基点別に2つの部分配列に分割します.

征服(Conquer)
部分をきちんと並べる.

合併(Combine)
配置された部分の配置を1つの配置にマージします.

「無限ループ」の可能性はありますか?
👉 ループ呼び出しを行うたびに、少なくとも1つの要素が最終的に位置を決定するため、アルゴリズムが必ず終了することを保証することができる.

時間の複雑さ

平均:O(nloḡn)

最悪:O(n^2)

周知のように、ソートの中で最も速いアルゴリズムは1、2を数えて急速にソートすることですが、すべての場合に有利ですか?
例)並べ替えが行われた場合:
配列が[1,2,3,4]の場合,1を基点として2つの部分配列に分割するには4回の演算が必要である.現在1より小さい配列はなく、大きい配列は[2,3,4]であるため、[2,3,4]で割ると3回の演算が必要になる...
これで合計4+3+2+1となり,O(n^2)の時間的複雑さが得られる.
👉 この場合、挿入ソートはクイックソートよりも速いです.

最も重大な時間の複雑さを回避する方法

ランダム化
配列内のランダムな2つのインデックスを逆さまにして、配列を整列させません.

ランダム基点の選択
乱数を生成するようにデータム点を選択すると、ソートされた配列またはソートに近い配列で最も悪い値を選択する回数が減少します.

Median Of Three Pivot
基準点を選択する場合、候補として3つの要素を選択し、中間値を選択することで、基準点を選択し、最悪の場合は避けることができます.

クイックソートの例

クイックソートコード

const quickSort = (arr) => {
  if(arr.length === 0)
    return [];
  const left = [];
  const right = [];
  const pivot = arr[0];
  for(let i=1; i<arr.length; i++){
    if(pivot > arr[i])
      left.push(arr[i]);
    else
      right.push(arr[i])
  }
  return quickSort(left).concat(pivot, quickSort(right));
}