ソートアルゴリズムの最もコストの高い操作は何ですか？スワップ操作か比較操作ですか？ソートの最もコストのかかる操作
私はそれが交換していると思ったが、私の友人はその比較を考えている。その比較を正当化できる唯一の方法は、すべての要素を比較する必要があるが、すべての要素をスワップする必要がないということです（要素がすでに正しい位置にある場合、スワップする必要はありません）。したがって、全体的に見ると、コストのかかるスワップよりも安価な比較があります。しかし、私は答えが不明です。何かご意見は？
すべてがRAMに格納されていると仮定すると、スワップ操作は比較操作よりも原子的に高速です。 （2つの読み取りと2つの読み取り、2つの書き込みとその間のすべてのレジストリ操作を含む）。
これは明らかにソートアルゴリズムに依存しますが、要素が少なくても比較的頻繁にスワップするため、比較が少ないものもあります。
いくつかの比較を行い、すべての要素を比較してバブルソートのような単純なアルゴリズムを交換し、すべての要素を互いに比較してあまり頻繁にスワップしないクイックソートを実行します。それはまた、ベース配列に依存します。すべてが既にソートされている場合、バブルソートは何もスワップしませんが、すべてを比較しますが、ヒープソート（たとえば）はすべて「スワップ」する必要があります。
最後に、スワップ操作の平均回数（スワップ操作の時間コスト）/（平均操作回数）（comp操作の時間コスト）はアルゴリズムの見積もりがかなり難しく、より多くのアルゴリズムすべてに外挿する必要があります。
ソートアルゴリズムのスワップコストは常に比較コストよりも高いと個人的には思っていますが、その証拠をバックアップすることはできません（これは単なる個人的な洞察です）。
すべてがRAMに入っているときにスワップするのが明らかに分かりません。（ – Bugaboo
ページファイルなどの概念は含まれていないので非常に単純化されています。 2つの値を比較して両方の値を比較し、ALUを使用して2つの値を比較する必要があります。スワップするには、2つのRAMアドレスをレジストリに覚えてから、両方の値を他のレジストリに入れ、 2番目の値などを書くための最初の値のアドレスなどです。私はなぜそれが長くかかるのかを説明することができますが、私はサイクル、マイクロコードなどのような他の概念を説明しなければならないでしょう。 – AdrienNK
予防措置システムでは、複雑な別のレイヤーを追加する高度なパイプライニングを使用します。このテーマに関するすべてのことを本当に知りたい場合は、なぜなら、それは操作のコストを考えるときに本当に重要なことなのですから。あなたがすでに説明しやすいいくつかのアセンブリをすでに持っているなら。 – AdrienNK
です。ディスクベースのデータの場合、主な要因は、ディスクページをメモリに格納するために必要なI/Oです。一度ページがあれば、CPUは比較的無料です。小さいキー（ints）の場合、スワップは比較よりもコストがかかるかもしれません。非常に小さな要素サイズの場合、メモリ（キャッシュ）の局所性が支配的になる可能性があります。 – wildplasser
（ワイルドカードからの続き）...これは、ディスク（または仮想メモリ）上に存在するリストの交換がよりコストがかかることを意味します。しかし、リストがキャッシュメモリ内にある場合、スワップと比較はほぼ同様の費用であり、すべてのスワップまたはすべての比較の累積コストは、使用するアルゴリズムによって異なります。 –