私が知っているすべてのソートアルゴリズムは、彼らが作業するデータ構造への排他的アクセスを必要とします。いつでも変更できるデータを処理できる人はいますか？変更可能なデータを（およそ）ソートするアルゴリズムはありますか？
すべてでこれを可能にするために、我々は確かに想定することができます。
私は上記のものよりも多かれ少なかれ厳しい前提がある場合でも、情報、論文または実装に興味があります。
多くの多くのデータ構造がソート順にデータを維持します。たとえば、任意のツリー、スキップリスト、ヒープなどは、順序付けられたアクセスを許可します。一般に、データ項目の挿入、削除または更新は、O（ログN）以上（N =データセット内の項目数）です。したがって、ある時間間隔でデータセットのソートされた不変量をO（M * log（N））に維持するコストを期待できます。ここで、Mは、その時間間隔で挿入/削除/更新するアイテムの数です。
一部の並べ替えアルゴリズム（挿入ソートなど）は、データが部分的にソートされている場合に、よりよく機能します。最高でも、そのようなアルゴリズムを実行するコストはO（N）ですが、これは非常に限られた状況でのみ発生します。平均して、それはO（N * log（N））に近いと期待できます。
したがって、データセットのソートの不変量を常に維持する必要がある場合は、インデックスやヒープのようなデータ構造を使用する必要があります。ただし、データを必要な場合にのみ、更新をバッファにバッファリングし、必要に応じてデータセット全体を再ソートする方が効率的です。
私は、「揮発性」のコンテンツ、つまり構造が操作を実行している間に変更されるコンテンツ（通常の（排他的アクセス）構造とアルゴリズムではできないコンテンツを処理できるデータ構造を特に探しています。 ）。より複雑なプロセスの境界は軽微であり、例えばO（n^3）内のものはすべて私にとってうまくいくでしょう。 – mafu
ほとんどの比較/交換ソートでは、ほとんどの場合、変更されている配列をソートできるはずです。挿入ソートとシェルソートは確かにできます。バブルソートや選択ソートも可能です。私はQuicksortについて完全にはわからない。ソートの途中でデータ値が変更された場合、いくつかの実装が無限ループに陥る可能性があります。
単純な挿入の場合を考えてみましょう。配列[4, 7, 5, 3, 2]から始めます。
数回反復した後は、[3, 4, 5, 7, 2]となります。この時点で、誰かが入り込んで4を1に変更し、[3, 1, 5, 7, 2]となります。あなたの並べ替えは、最後の項目、2を配置しようとしています。最終的には[3, 1, 2, 7, 5]となります。最後の配列は最終的な配列のようになります。
頻繁に変更されない配列では、いくつかのアイテムが不足している可能性が高く、挿入ソートではすぐに物事を整理できます。
あなたの実装には注意が必要です。他のスレッドが配列を変更する可能性があるため、配列項目の内容を保持する一時変数を持つことはできません。配列内の項目が変更されない参照（つまり、参照されているものだけが配列内の要素ではなく変更可能）である場合、その参照を一時的に保持することは問題ありません。しかし、もし配列が、例えば整数の配列なら、すべての比較は一時的な値を保持するのではなく、実際の配列要素に対して行わなければなりません。
つまり、このようなことはかなり珍しいことです。多くの順序付けられたデータ構造は、複数のスレッドが同時に読み書きすることができるようにロックフリーになるようにコーディングすることができます。これにより、データ構造が常に順序を維持するため、「ほぼ」ソートする必要がなくなります。
[私は出版物について知らない]このようなことは、注文が比較的安定的かつ比較的重要でない場合に発生する。例：候補者がチェスエンジン内の特定の位置に移動し、コストまたは利益によって発注されます。または、シミュレーションで確率的ベクトルを使用した重み付きサンプリング。多くの場合、1パスのバブルソート、または挿入/選択の種類のスキームが使用されます。 – wildplasser