algorithm - アメリカ国旗ソートの最適化

Question

アメリカン バケット ソートを実装しようとしています。Wiki には、「まず各ビンに入るオブジェクトの数を数え、次に各オブジェクトをバケットに入れる」と書かれています。

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

Answer 1

http://en.wikipedia.org/wiki/American_flag_sortを意味すると仮定すると、記事の上部で指摘されているように、これをインプレースで実行できます (ただし、これは安定した並べ替えではありません)。主なアイデアは、読み込まれていない最初のアイテムへのポインター (最初は 0) と、1 つのアイテムを保持する一時変数を持つことです。

最初のステップとして、ポインターを見て、ポインターが指しているアイテムを拾います。これで、インデックスを使用して配置できます。その場所が最初に読んだ位置でない限り、別のアイテムを上書きしようとしているので、拾ったアイテムを上書きするアイテムと交換し、別の一時的なアイテムを保持しています-そして見上げますどこに行って続行する必要があります。

最終的に、読み取り元の場所に何かを配置したので、読み取りポインターをインクリメントして、既にソートされたアイテムを書き込んだ領域をスキップし、別のアイテムを取得して、すべてがソートされるまで続行できます。