クイック ソートは最も効率的なアルゴリズムの 1 つであり、分割統(tǒng)治手法を使用して配列をソートします。

クイックソートの仕組み

クイック ソートの主なアイデアは、ソートされていない配列內の正しい位置に一度に 1 つの要素を移動できるようにすることです。この要素はピボットと呼ばれます。

:

の場合、ピボット要素は正しい位置にあります。

1. その左側の要素はすべて小さくなります。
2. その右側の要素はすべて大きくなります。

左の數(shù)字がソートされているか右の數(shù)字がソートされているかは関係ありません。重要なのは、ピボットが配列內の正しい位置にあることです。

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

これらはすべて、ピボットが 23 である配列の有効な出力です。

ピボットの正しい位置を見つける

クイック ソートは、ピボットが配列內で正しい位置を見つけるのに役立ちます。たとえば、ピボットが配列の先頭に配置されているものの、最小の數(shù)値ではない場合、クイック ソートは、配列內に 5 つの小さな要素のためのスペースを確保するために 5 ステップ移動する必要があると判斷します (そのような要素が 5 つあると仮定します)。數(shù)字。

配列 [10, 4, 15, 6, 23, 40, 1, 17, 7, 8] があり、10 がピボットであるとします:

この時點:

• 數(shù)字の 10 は、自分が正しい位置にいるのか、そこに到達するために何歩移動する必要があるのか??わかりません。クイック ソートは、10 と次のインデックスの値を比較することから始まります。
• クイック ソートは、4 が小さいことを確認すると、ピボットを 1 歩前に移動して 4 が前に來るようにする必要があることを記録します。
• したがって、numberOfStepsToMove は 1 増加します。

次に、インデックス 2 の値は 15 で、10 より大きくなります。調整の必要がないため、クイック ソートはステップ數(shù)を変更せずに維持し、配列內の次の要素に進みます。

次のインデックスでは、値は 6 で、10 より小さくなります。ピボットは 2 つの小さい數(shù)値 (4 と 6) 用のスペースを確保する必要があるため、クイック ソート はステップ數(shù)を 2 に増やします .

ここで、配列の左側に小さい數(shù)字を並べて保持するには、6 を 15 と交換する必要があります?，F(xiàn)在のインデックスとnumberOfStepsToMoveの値に基づいて數(shù)値を交換します。

Quick Sort は配列のループを継続し、ピボットより小さい數(shù)値の數(shù)に基づいて、numberOfStepsToMove を増やします。これは、ピボットを正しい位置に移動する必要がある距離を決定するのに役立ちます。

numberOfStepsToMove は 23 または 40 では変わりません。どちらの値もピボットより大きく、配列內でその前に來るべきではないためです。

ここで、Quick Sort がインデックス 6 の値 1 にループすると、numberOfStepsToMove が 3 に増加し、インデックス 3 の數(shù)値と交換されます。

クイックソートは、配列の最後に到達するまでこのプロセスを継続します:

配列の最後に到達したので、10 より小さい數(shù)値が 5 つあることがわかります。 したがって、ピボット (10) は、すべての數(shù)値よりも大きい正しい位置まで 5 ステップ移動する必要があります。その前の數(shù)字。

コード內でどのように見えるか見てみましょう:

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

ピボットを配置する場所を見つけるのに役立つ関數(shù)ができたので、Qucik Sort がどのように配列を小さな配列に分割し、getNumberOfStepsToMove 関數(shù)を利用してすべての配列要素を配置するかを見てみましょう。

const getNumberOfStepsToMove = (arr, start = 0, end = arr.length - 1) => {
  let numberOfStepsToMove = start;
  // we're picking the first element in the array as the pivot
  const pivot = arr[start];

  // start checking the next elements to the pivot
  for (let i = start + 1; i <= end; i++) {
    // is the current number less than the pivot?
    if (arr[i] < pivot) {
      // yes - so w should increase numberOfStepsToMove
// or the new index of the pivot
      numberOfStepsToMove++;

      // now swap the number at the index of numberOfStepsToMove with the smaller one
      [arr[i], arr[numberOfStepsToMove]] = [arr[numberOfStepsToMove], arr[i]];
    } else {
      // what if it's greater?
      // do nothing -- we need to move on to the next number
      // to check if we have more numbers less that pivot to increase numberOfStepsToMove or not
    }
  }

  // now we know the pivot is at arr[start] and we know that it needs to move numberOfStepsToMove
  // so we swap the numbers to place the pivot number to its correct position
  [arr[start], arr[numberOfStepsToMove]] = [
    arr[numberOfStepsToMove],
    arr[start],
  ];

  return numberOfStepsToMove;
};

クイック ソートは再帰を利用して配列をより小さなサブ配列に効率的に分割し、要素をピボットと比較して確実にソートします。

function quickSort(arr, left = 0, right = arr.length - 1) {
  // pivotIndex the new index of the pivot in in the array
  // in our array example, at the first call this will be 5, because we are checking 10 as the pivot
  // on the whole array
  let pivotIndex = getNumberOfStepsToMove(arr, left, right);
}

• アルゴリズムは、ピボットよりも小さい要素を含む左側の部分配列を再帰的に並べ替えます。
• 部分配列の要素が 1 つまたは 0 になると、すでにソートされているため、再帰は停止します。

次に、配列の右側に対して同じプロセスを実行する必要があります。

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

この例では、右側はすでにソートされていますが、アルゴリズムはそれを認識していないため、そうでなければソートされていたでしょう。

以上がクイックソートアルゴリズムを學ぶの詳細內容です。詳細については、PHP 中國語 Web サイトの他の関連記事を參照してください。