algorithm - 大きな配列の場合、選択ソートは挿入よりも高速ですか?

Question

重複の可能性:
挿入ソート vs バブルソート vs 選択ソートの効率?

大きな配列の場合、選択ソートは挿入よりも高速ですか? 最悪の場合はいつですか？

挿入は選択よりも速いことは知っていますが、大規模な配列の場合、最悪の場合はどうなりますか?

Answer 1

ウィキペディアの記事によると、

一般に、挿入ソートは配列にO（n2）回書き込みますが、選択ソートはO（n）回だけ書き込みます。このため、EEPROMやフラッシュメモリなど、メモリへの書き込みが読み取りよりも大幅にコストがかかる場合は、選択ソートが適している場合があります。

これは、アレイのサイズに関係なく当てはまります。実際、アレイが大きくなるにつれて、違いはより顕著になります。