ここで、ソートアルゴリズムの一つであるクイックソートを紹介します。
本説明では、配列の最後の要素をピボットとして選択するバージョンを紹介します。
クイックソートのアルゴリズムの手順は以下の通りです：
- 配列の最後の要素をピボットとして選択します。
- 配列を2つの部分配列に分割します：一つはピボットより小さい要素を含む部分配列、もう一つはピボット以上の要素を含む部分配列です。分割後、ピボット要素はこれら2つの部分配列の間に配置されます。
- ピボットより小さい要素の部分配列と、ピボット以上の要素の部分配列に対して、上記の手順を再帰的に適用します。この再帰処理は、各部分配列の要素数が1以下になるまで続きます。
- 再帰呼び出しがすべて完了すると、配列全体は昇順にソートされます。
Pythonのコードは以下の通りです：
26行目では、quick_sort関数を呼び出し、配列変数を引数として渡していることがわかります。これにより、その配列に対してインプレースでクイックソートが実行されます。
次に、21行目を見ると、quick_sort関数の中でqs関数が呼び出されています。qs関数は3つの引数を取ります。1つ目は配列arr、2つ目は左ポインタ、3つ目は右ポインタです。つまり、qs関数の役割は、配列arrのうち、左から右（両端を含む）までの部分配列に対してクイックソートを実行することです。
例えば、arrが[-2, 3, -1, 5, 4, -3, 0]、leftが2、rightが5の場合、インデックス2から5までの部分配列をソートすることを意味します。
その結果は、[-2, 3, -3, -1, 4, 5, 0]となります。
したがって、21行目でarr, 0, len(arr) - 1を引数として渡している場合、配列全体に対してクイックソートを実行していることを示します。
では、qs関数について見ていきましょう。この関数は再帰関数であるため、まずベースケースを考える必要があります。ベースケースはleft >= rightの場合です。なぜでしょうか？
left == rightの場合、その部分配列は要素が1つだけであり、すでにソート済みであるため、これ以上の処理は不要です。
一方で、left > rightの場合は、その部分配列が空であることを意味します。
したがって、left >= rightのときは、そのままreturnすればよいです。
もしleft < rightであれば、15行目にあるpartition関数を呼び出す必要があります。
partition関数は、arr, left, rightを引数に取り、配列arrの中のインデックスleftからright（両端含む）までの部分配列に対してパーティション処理を行います。
このパーティション処理では、部分配列の中から1つの要素をピボットとして選択します。このアルゴリズムでは、最後の要素をピボットとして選びます。すると、部分配列は次のような形に分割されます：
[ピボットより小さい要素, ピボット, ピボット以上の要素]
その後、partition関数はピボットのインデックスを返します。
ここで、arr = [-2, 3, -1, 5, 4, -3, 0]、left = 0、right = 6の場合を例に取り、partition関数内の処理全体を見ていきましょう。
まず、ピボットとして配列の最後の要素（0）を選択します。
変数iをleft - 1で初期化します。
したがって、初期状態では j の値は 0 となります。
値の -2 はピボット（0）より小さいため、i を 1 増やす必要があります。
次に、i と j が指している要素を交換する必要があります。
しかしこの時点では、i と j は同じ要素を指しているため、実際には変化はありません。
次に、j はインデックス1に移動します。3はピボット（0）より小さくないため、交換は不要です。
次に、j はインデックス2に移動します。
-1 はピボット（0）より小さいため、i を 1 増やす必要があります。
次に、i と j が指している要素を交換する必要があります。
次に、j はインデックス3に移動します。5はピボット（0）より小さくないため、交換は不要です。
次に、j はインデックス4に移動します。4はピボット（0）より小さくないため、交換は不要です。
次に、j はインデックス5に移動します。
-3 はピボット（0）より小さいため、i を 1 増やす必要があります。
次に、i と j が指している要素を交換する必要があります。
その後、for ループを終了します。
次に、i+1 が指す要素と right が指す要素を交換する必要があります。
その後、partition 関数は i+1 を返します。これがパーティション処理後のピボットの位置です。
最後に、16行目でピボットの左側の部分配列に対してクイックソートを実行し、17行目でピボットの右側の部分配列に対してクイックソートを実行します。
時間計算量
では、このアルゴリズムの時間計算量はどうなるのでしょうか。
最悪ケース、最良ケース、平均ケースのシナリオを考えてみます。
最悪ケース
配列がすでに昇順にソートされている場合（例：[1, 2, 3, 4, 5, 6, 7]）、qs 関数を left = 0、right = 6 で呼び出すとします。
パーティション処理の後、配列は変わらず、ピボットのインデックスは6のままです。
次に、ピボットを除いた部分配列に対して再度 qs 関数を呼び出す必要があります。この場合、left = 0、right = 5 で qs 関数を呼び出します。
この処理が残りの部分配列に対して再帰的に続きます。
したがって、qs 関数の呼び出し順序は次のようになります：
qs(arr, 0, 6) → qs(arr, 0, 5) → qs(arr, 0, 4) → ... → qs(arr, 0, 0)
つまり、qs 関数で確認する要素の数は次のように変化します（配列全体の長さを n とした場合）：
n → n-1 → n-2 → ... → 1
では、partition 関数内の for ループの繰り返し回数はどう計算するのでしょうか。
確認する要素の数が n の場合、for ループの繰り返し回数は n-1 ですが、概算すると約 n と考えられます。
アルゴリズム全体での繰り返し回数を求めるには、上の図にあるすべての部分配列の繰り返し回数を合計する必要があります。
これを計算すると (n + 1) * n / 2 となり、時間計算量は O(n²) です。
最良ケース
もし選んだピボットが常に中央値となり、ピボットより小さい要素の数とピボット以上の要素の数が等しい場合、qs 関数で処理される配列要素の数の変化は、以下の図のようになります：
そして各レベルにおいて、partition 関数の for ループで必要な繰り返し回数は常に n となります。
そして、レベルの数は log n です。
したがって、最良ケースの全体の時間計算量は、O(n) と log n を掛け合わせることで求められ、O(n log n) となります。
平均ケース
以下の2つの前提を置きます：
- 配列に重複する値はない。
- 配列内の要素の順序はランダムである。
この場合、時間計算量の平均ケースは O(n log n) となります。
参考文献:
- A Complete Overview of Quicksort by CS Dojo