アメリカンフラグの並べ替えの最適化

Question

アメリカンバケットソートを実装しようとしています。ウィキは「各ビンに落ちるオブジェクトの数を最初に数え、次に2番目に各オブジェクトをそのバケツに入れる」と言っています。

第2段階では、オブジェクトを適切なバケットに配置するとき、補助配列を使用する必要がありますか？線形時間で配列要素を交換することでこれを行う方法はありますか？

Answer 1

http://en.wikipedia.org/wiki/American_flag_sortを意味すると仮定すると、記事が上部を指し示すように、これをインプレースで実行できます（これは安定したソートではありませんが）。主な考え方は、読み込まれていない最初の項目へのポインタ（最初は0）と1つの項目を保持する一時変数を持つことです。

最初の手順として、ポインタを見てアイテムをピックアップします。これで、インデックスを使用して適切な場所に配置できます。その場所が元々読んでいた位置でない限り、別のアイテムを上書きしようとしているので、あなたが上書きしたアイテムと取り込んだアイテムを入れ替えるので、別の一時アイテムを保持しています。それはどこに行かなければならないのか。

最終的には、読み込んだ場所に何かを配置しているので、読み込みポインタを増やしたり、並べ替えられた項目を書き込んだ箇所をスキップしたり、別の項目を選択したり、