Cyclic Partition: 最大 1.5 倍高速なパーティション分割アルゴリズム

コンピューター・プログラミングにおける基本的なアルゴリズムであるシーケンス・パーティショニングは、ピボット・バリューに基づいてシーケンス内の数字を再配置することを目的としています。ピボット・バリュー未満の数字をまず配置し、残りの数字を続けることを目指しています。パーティショニングの応用例として、クイックソートやシーケンスの中央値の探索などがあります。現在、2つの有名なパーティショニング・アルゴリズムがあります。ひとつはロムート・スキーム、もうひとつはホア・スキームです。ホア・スキームは、実際には配列内の再配置を少なくするためによく好まれます。新しいパーティショニング・スキームとして「サイクリック・パーティショニング」が提案されており、ホア・スキームに似ていますが、1.5倍少ない再配置を行います。サイクリック・パーティショニング・スキームは、初期状態で場所が不適切な値の数に近づくアサインメントの数になるため、ほぼ最適と考えられます。ホア・スキームのレビューでは、時間複雑さがO(N)であり、2つのスキャンがどこで会うかに関係なく同じです。ホア・スキームでは、L/2の3倍のアサインメントが必要であり、Lは場所が不適切な値の数です。アサインメントのサイクルという概念が導入され、ホア・パーティショニング・スキームの最適化に必要です。左シフトやシーケンスの逆順など、異なる再配置のケースが提示され、ある再配置が他よりも多くのアサインメントを必要とすることを示しています。