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

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

クイックソートの仕組み

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

:

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

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

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

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

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

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

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

この時点:

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

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

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

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

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

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

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

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

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

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

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

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

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 サイトの他の関連記事を参照してください。