データ構造とアルゴリズム-クイックソート

クイックソートは非常に効率的なソートアルゴリズムであり、データの配列をより小さな配列に分割することに基づいています。大きな配列は2つの配列に分割され、1つは指定された値よりも小さい値、たとえばピボットを保持し、別の配列はピボット値よりも大きい値を保持します。

クイックソートは配列を分割し、それ自体を2回再帰的に呼び出して、結果の2つのサブ配列をソートします。このアルゴリズムは、平均サイズと最悪ケースの複雑度がそれぞれO（nLogn）とimage.png（n ^ 2 ^）であるため、大規模なデータセットに対して非常に効率的です。

クイックソートのパーティション

次のアニメーション表現は、配列内のピボット値を見つける方法を説明しています。

クイックソートパーティションアニメーション

ピボット値は、リストを2つの部分に分割します。そして再帰的に、すべてのリストに要素が1つだけ含まれるまで、各サブリストのピボットを見つけます。

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

クイックソートでのパーティション分割の理解に基づいて、次のようなアルゴリズムの作成を試みます。

Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot

クイックソートピボット擬似コード

上記のアルゴリズムの擬似コードは、次のように導出できます-

function partitionFunc(left, right, pivot)
   leftPointer = left
   rightPointer = right - 1

   while True do
      while A[&plus;&plus;leftPointer] < pivot do
        //do-nothing
      end while

      while rightPointer > 0 && A[--rightPointer] > pivot do
        //do-nothing
      end while

      if leftPointer >= rightPointer
         break
      else
         swap leftPointer,rightPointer
      end if

   end while

   swap leftPointer,right
   return leftPointer

end function

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

ピボットアルゴリズムを再帰的に使用すると、パーティションが小さくなります。その後、各パーティションはクイックソートのために処理されます。次のようにクイックソートの再帰アルゴリズムを定義します-

Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively

クイックソート擬似コード

それにもっと入るには、クイックソートアルゴリズムの擬似コードを見てみましょう-

procedure quickSort(left, right)

   if right-left <= 0
      return
   else
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition&plus;1,right)
   end if

end procedure

Cプログラミング言語でのクイックソートの実装については、リンク：/data_structures_algorithms/quick_sort_program_in_c [ここをクリック]をご覧ください。

Data-structures-algorithms-quick-sort-algorithm

目次