performance - 配列を読み取ってからソートするか、ソートする方が速いですか?

Question

Pascalでプログラミングしています。

配列を読み取ってから並べ替える (たとえば、クイック 並べ替えを使用する) のと、読み取り中に並べ替えるのとでは、どちらが高速ですか? ソートされていない配列はもう必要ないので、読み取ったときに配列の順序を変更できます。

Answer 1

最後に配列全体をソートすることがデフォルトの選択です。

配列を読んでいるときに配列を段階的に並べ替えても、まったく何も得られません。ただし、失われているのは、ジョブに最適な並べ替えアルゴリズムを選択する柔軟性です。

Answer 2

これを参照してください：クイックソートと挿入ソートの平均時間計算量

読みながらソートしているように、挿入ソートになります。問題は、どちらのソートが速いかということです。

読み取りにはo（n）時間しかかからず、ソートの複雑さよりも短くなります（O（nlogn）したがって、読み取りは重要ではありません。

Answer 3

配列全体を読み取り、並べ替えます。それ以外の場合は、ヒープを使用して、読み取り中にソートされた構造またはより多くのスペースと時間がかかるその他の構造に保持する必要があります。