ソートされた文字列内の指定されたインデックスにある文字を、ハッシュやソートなしで判別する方法はありますか？

Question

文字列と整数が与えられています。文字がソート順に配置される場合、の文字がの整数位置の文字列内にあるかどうかを指定する必要があります。

例について

String = LALIT 
Index = 3 
Sorted string AILLT and the character at position 3 is L 

それはソートせずに、この問題を解決することは可能ですか？
の場合、疑似コードを提供できます。

Answer 1

はい、可能です。 selection algorithmという名前のものを探しています。要素のリストと数字がkの場合、要素がソート順である場合は、どの要素が位置kになるかを返します。驚くべきことに、リスト全体をソートせずにこれを行うことは可能です！

選択のための最も単純なノンソートアルゴリズムは、予期される時間O（n）で実行され、元の配列を変更することが許されている場合はO（1）補助記憶域だけを使用します。quickselectと呼ばれます。 quickselectの背後にあるアイデアは、ピボット要素を選択し、要素をピボットよりも小さい要素、ピボットと等しい要素、ピボットよりも大きな要素に分割してから、それに基づいて何が起こるかを確認することです。ピボット要素がこのステップの後にkの位置に終わると、終了します。これは、最終シーケンスの kの位置にある要素です。ピボットがkより高い位置にある場合は、ピボットの左を再帰的に見てください（最も小さい要素のは最小の要素のどこかにあります）。ピボットがよりも低い位置に再帰的にある場合ピボットの右側を見てください（k最も小さい要素がそこにあります）。

メジアン・オブ・メジアンアルゴリズムのように、最悪の場合は常にO（n）時間で実行されますが、古典的な「頭を包むトリッキーなアルゴリズム」など、他のアプローチもあります。