ソートアルゴリズムの中で最もコストのかかる操作は何ですか? スワップ操作ですか、それとも比較操作ですか。
スワッピングだと思ったのですが、友達は比較だと思っています。比較がコストのかかる操作であることを正当化できる唯一の方法は、すべての要素を比較する必要がありますが、すべての要素を交換する必要はないということです (つまり、要素が既に正しい位置にある場合、交換する必要はありません)。したがって、全体像としては、コストのかかるスワップよりも安価な比較が多くなります。しかし、私は答えがわかりません。何かご意見は？
すべてが RAM で行われると仮定すると、スワップ操作は比較操作より原子的に高速です。（これは明らかです。2回の読み取り、次にCPU操作と、2回の読み取り、2回の書き込み、およびレジストリ操作を含むその間のすべて）。
それは明らかにソートアルゴリズムに依存します。要素が少ないために比較が少なくなるものもありますが、比較的頻繁に交換されます。
比較をほとんど行わないクイックソートを使用してから、ほとんどすべてを交換し、バブルソートのような単純なアルゴリズムを使用して、すべての要素を互いに比較し、交換の頻度を減らします。それはベース配列にも依存します。すべてがすでにほぼソートされている場合、バブルソートは何もスワップしませんが、すべてを比較しますが、ヒープソート（たとえば）はすべてを「スワップ」する必要があります。
最後に、(スワップ操作の平均回数) (スワップ操作の時間コスト)/(comp 操作の平均回数) (comp 操作の時間コスト) をアルゴリズムで見積もるのは非常に難しく、アルゴリズム。
個人的には、すべてのソート アルゴリズムのスワップ コストは常に比較コストよりも高いと考えていますが、その主張を証拠で裏付けることはできません (これは単なる個人的な洞察です)。