広告
クイックソートは非常に効率的なソートアルゴリズムであり、データの配列のパーティション化に基づいていますより小さな配列に。大きな配列は2つの配列に分割され、そのうちの1つは指定された値よりも小さい値、たとえばピボットを保持します。これに基づいてパーティションが作成され、もう1つの配列はピボット値よりも大きい値を保持します。
クイックソートは次に、配列を2回再帰的に呼び出して、結果の2つのサブ配列を並べ替えます。このアルゴリズムは、平均および最悪の場合の複雑さがそれぞれO（n2）であるため、大規模なデータセットに対して非常に効率的です。
クイックソートのパーティション
次のアニメーション表現は、その方法を説明しています。配列内のピボット値を検索します。
ピボット値は、リストを2つの部分に分割します。そして、すべてのリストに要素が1つだけ含まれるまで、各サブリストのピボットを繰り返し見つけます。
クイックソートピボットアルゴリズム
クイックソートでのパーティショニングの理解に基づいて、次に、次のようなアルゴリズムを記述してみます。
Step 1 − Choose the highest index value has pivotStep 2 − Take two variables to point left and right of the list excluding pivotStep 3 − left points to the low indexStep 4 − right points to the highStep 5 − while value at left is less than pivot move rightStep 6 − while value at right is greater than pivot move leftStep 7 − if both step 5 and step 6 does not match swap left and rightStep 8 − if left ≥ right, the point where they met is new pivot
クイックソートピボット擬似コード
上記のアルゴリズムの擬似コード−
クイックソートアルゴリズム
ピボットアルゴリズムを再帰的に使用すると、可能なパーティションが小さくなります。次に、各パーティションはクイックソートのために処理されます。クイックソートの再帰的アルゴリズムを次のように定義します-
Step 1 − Make the right-most index value pivotStep 2 − partition the array using pivot valueStep 3 − quicksort left partition recursivelyStep 4 − quicksort right partition recursively
クイックソートの擬似コード
詳細については、クイックソートの擬似コードを参照してください。ソートアルゴリズム-
Cプログラミング言語でのクイックソートの実装については、ここをクリックしてください。
広告