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

クイックソートの仕組み

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

:

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

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

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

// 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 である配列の有効な出力です。

ピボットの正しい位置を見(jiàn)つける

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

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

この時(shí)點(diǎn):

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

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

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

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

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

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

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

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

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

コード內(nèi)でどのように見(jiàn)えるか見(jiàn)てみましょう:

// 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]

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

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);
}

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

次に、配列の右側(cè)に対して同じプロセスを?qū)g行する必要があります。

// 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]

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

以上がクイックソートアルゴリズムを?qū)Wぶの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國(guó)語(yǔ) Web サイトの他の関連記事を參照してください。