Algorithms In A Nutshell本で選択ソートについて読んでいます。本書には次のように書かれています。
選択ソートは、すべてのソート アルゴリズムの中で最も低速です。ある反復から次の反復まで何も学習せずに、ほぼ同じタスクを繰り返し実行します。A で最大の要素 max を選択するには n-1 回の比較が必要で、2 番目に大きな要素を選択するには n-1 回の比較が必要です。これらの比較の多くは無駄になります。なぜなら、要素が 2 番目より小さい場合、それが最大の要素になる可能性はなく、したがって最大値の計算に影響を与えないからです。
太字のテキストはどういう意味ですか?
誰かが簡単な例で説明できますか?
あなたの本の著者は、複雑で長い文章が好きなようです。彼からそれを学ばないでください。読者を混乱させる方法を知っている人はすでに十分にいます。
理解しやすくするための試み:
A から最大の要素を選択するn-1と、A に要素がある場合に比較が行われnます。残念ながら、並べ替えアルゴリズムはこの情報を再利用しません。
残りの要素を並べ替えるために内側のループを再度開始するときは、別のn-2比較が必要です (最後のループで 1 つの要素が正しい場所に並べ替えられています)。
並べ替えは内側のループの実行ごとに 1 つの要素のみを移動するため、ほとんどの比較は、結果に対して何もせずに何度も何度も繰り返されます。これは単なる時間の無駄です。
ウィキペディアには、選択ソートがどのように機能するかという素晴らしいアニメーションがあります。