ソートされた double のセットがあるとします。
{ 0.124, 4.567, 12.3 }
コードの別の部分によってゼロ以外の正の double が作成され、ソートされたままこのセットに挿入する必要があります。たとえば、作成された double が の7.56
場合、最終結果は次のようになります。
{ 0.124, 4.567, 7.56, 12.3 }
私のコードでは、この「double を作成してソート済みセットに挿入する」プロセスが何度も繰り返されます。おそらく50万回から100万回。合計でいくつの double が正確に作成されるかはわかりませんが、上限はわかっています。
試み
私の素朴な最初のアプローチは、長さ = 上限の配列を作成し、それをゼロで埋めてから、最初の double のセットを追加することでした (「追加」= 0 値のエントリを double に置き換えます)。double が作成されるたびに、それを配列に追加して挿入ソートを実行します。これは、順序付けられた配列のソートに適しています。
質問
500k から 100 万の挿入スロットを実行すると、深刻なパフォーマンスの問題になると感じています。(または私は間違っていますか?) C でこれを行うためのより効率的なデータ構造やアルゴリズムはありますか?
編集:
セットをソートしたままにしておく理由は、「double を作成してソート済みセットに挿入する」プロセスのたびに、そのセット内の最小の要素を検索できるようにする必要があるためです (そして、それを 0 に置き換えて削除する可能性があります)。 )。これを行う最善の方法は、セットをソートしておくことだと思いました。
しかし、そうでない場合、おそらく代替手段はありますか?