1. 概要

効率的な並べ替えアルゴリズムは、問題の複雑さを軽減する上で重要な役割を果たします。 並べ替えアルゴリズムは、コンピュータサイエンスのさまざまな問題で使用され、入力配列またはリストの要素を昇順または降順で再配置します。

Quicksort は、分割統治法に基づく非常に効率的な並べ替えです。

このチュートリアルでは、クイックソートアルゴリズムの最悪のシナリオについて詳しく説明します。

2. クイックソートの最悪のケースはいつ発生しますか?

クイックソートアルゴリズムの効率は、ピボット要素の選択に大きく依存します。 クイックソートの入力がソートされた配列であり、ピボット要素として左端の要素を選択するとします。この場合、2つの非常に不均衡な配列があります。 1つの配列には1つの要素があり、もう1つの配列には要素があります。

同様に、指定された入力配列が逆に並べ替えられ、ピボット要素として右端の要素を選択すると、最悪のケースが発生します。 この場合も、ピボット要素は入力配列を2つの不平衡配列に分割します。

上記の2つの場合を除いて、指定された入力配列のすべての要素が同じである特別な場合があります。このようなシナリオでは、ピボット要素は入力配列を2つに分割できません。クイックソートの時間計算量は大幅に増加します。

3. 最悪の場合の時間計算量分析

可能な限り最も不均衡なパーティションを提供するような方法でピボット要素を選択するとします。

ボックス内のすべての数字は、アレイまたはサブアレイのサイズを示しています。

サイズの入力配列を考えてみましょう。 最初のパーティション呼び出しは、入力配列でパーティションステップを実行するのに時間がかかります。

各パーティションステップは、前のステップから再帰的に呼び出されます。 それを考えると、各パーティション呼び出しの複雑さを取り、それらを合計して、クイックソートアルゴリズムの全体的な複雑さを得ることができます。

したがって、最悪の場合のクイックソートアルゴリズムの時間計算量は次のようになります。

または、それを計算するための漸化式を作成することもできます。

最悪の場合、最初のパーティションの後に、一方の配列に要素があり、もう一方の配列に要素があります。 最悪の場合に要素をソートするための時間計算量を示しているとしましょう。

繰り返しますが、基本ケースの場合と、については、何もソートする必要はありません。 したがって、ソート時間は

これで、前に導出した漸化式を解く準備ができました。

, , , , , , ,

結果として、

4. 最悪のケースを回避する

適切なピボット要素を選択することで、クイックソートの最悪のケースを回避できます。 このセクションでは、ピボット要素を選択するさまざまな方法について説明します。

ピボット要素を選択するための最初のアプローチは、配列の中央からそれを選択することです。 このようにして、入力配列を、その中の要素の数がほぼ等しい2つのサブ配列に分割できます。

場合によっては、ランダムピボット要素の選択が適切な選択です。 クイックソートのこの変種は、ランダム化されたクイックソートアルゴリズムとして知られています。

ピボット要素を選択する別のアプローチは、3つのピボット候補の中央値を取得することです。この場合、最初に入力配列から左端、中央、右端の要素を選択します。 次に、それらを左側のパーティション、ピボット要素、および右側のパーティションに配置します。

5. 長所と短所

クイックソートは、効率の点で最高のソートアルゴリズムの1つと見なされています。 クイックソートの平均的なケース時間の複雑さは、マージソートと同じです。 入力配列が大きい場合でも、非常に優れたパフォーマンスを発揮します。 高性能を提供し、コーディングが比較的簡単です。 追加のメモリは必要ありません。

クイックソートの主な欠点は、ピボット要素の選択を誤ると、アルゴリズムの時間計算量がに減少する可能性があることです。 また、安定ソートアルゴリズムではありません。

6. 実装

クイックソートの実際を確認するには、Javaでのクイックソートの記事を参照してください。

7. 結論

このチュートリアルでは、クイックソートのさまざまな最悪のシナリオについて説明し、その時間計算量分析を示しました。