問題タブ [loop-invariant]

Quicksort アルゴリズムの一部の実装について、ループ不変条件の定義と証明に問題があります。これはロムート版でもホアレ版でもありません。

このように実装されている既知のバージョンの Quicksort について知っている場合は、お知らせください。

Python でのアルゴリズムの実装:

次のループ不変式を定義することができました (間違っている可能性があります)。

whileループの各反復の開始時にk、 array 内の各インデックスに対してA:

• もしk = pそうならA[k] = y

• もしp < k <= iそうならA[k] < y

• もしj <= k <= rそうならA[k] > y

whileループインpartition()メソッドのループ不変条件を定義して（上記が間違っている場合）、それを証明するのを手伝ってください。