教科書の Intro to Algorithms (CLRS) の問題 9-3 では、長さ n の配列の k 次の統計 (並べ替えた場合の配列の k 番目の要素) を見つけるための高速 O(n) アルゴリズムについて説明しています。 k が n よりもはるかに小さい場合。n が奇数の場合、このアルゴリズムの正しさについて確信が持てず、正しさを証明する方法を見たいと思っています。
基本的な考え方は、最初に配列を 2 つの半分に分割することです。1 つ目は floor(n/2) 要素、2 つ目は ceil(n/2) 要素です。次に、前半の各要素と後半の対応する要素を「組み合わせ」ます。n が奇数の場合、これは残りのパートナー化されていない要素を残します。
パートナーの各ペアについて、左のパートナーが右のパートナー以上であることを確認し、そうでない場合は 2 つを交換します。次に、後半の k 次統計量を再帰的に見つけ、前半の対応するスワップで後半に行われたすべてのスワップをミラーリングします。この後、配列全体の k 次統計量は、前半の最初の k 要素、または後半の最初の k 要素のいずれかになければなりません。
私の混乱は、配列の長さ n が奇数で、後半にパートナーのない要素が 1 つだけある場合に発生します。再帰は後半で実行され、唯一のパートナーのない最後の要素を含む、配列の最後の ceil(n/2) 要素で構成されるため、後半で行われたすべてのスワップを、対応する要素内で行われたスワップでミラーリングすることになっています。前半のパートナーは、パートナーがいないため、スワップの1つが最後の要素を含む場合に何をすべきかは不明です.
教科書では特に注意されていないようなので、最終要素が入れ替わる場合、前半は相手のミラームーブを一切行わないようにしていると思います。その結果、最後の要素は、交換した相手のパートナーを単に「盗む」だけです。ただし、この場合、アルゴリズムがまだ正しいかどうかを確認する簡単な方法はありますか? 最後の要素が他の誰かのパートナーを盗んだときに、そのパートナーが実際には k 次の統計であり、後でアクセスできない場所にスワップされた場合はどうなるでしょうか? 順序統計の選択に関係する再帰と分割のメカニズムは、私には十分に不透明であるため、自信を持ってそのシナリオを除外することはできません。