並べ替えに関する C++ による Robertsedwick のアルゴリズムを読んでいます
プロパティ 1: 挿入ソートとバブル ソートは、各要素に対応する反転の最大数が一定であるファイルに対して線形数の比較と交換を使用します。
別の種類の部分的に並べ替えられたファイルでは、並べ替えられたファイルにいくつかの要素を追加したか、並べ替えられたファイル内のいくつかの要素を編集してそれらの kesy を変更した可能性があります。挿入ソートは、そのようなファイルに対して効率的な方法です。バブルと選択ソートはありません。
プロパティ 2: 挿入ソートは、一定数以上の対応する反転を持つ、最大でも一定数の要素を持つファイルに対して線形数の比較と交換を使用します。
上記のプロパティに関する私の質問は
プロパティ 1 とプロパティ 2 の違いを取得できませんか? 誰かがここで私を説明できますか?
上記のプロパティ2の著者が言及した挿入ソートは、バブルおよび選択ソートではなく、どのような根拠に基づいていますか?
例を挙げて説明すると良いでしょう。
お時間をいただきありがとうございます。
したがって、ソート順の反転<はありますi < jがa[i] > a[j].
プロパティ 1. シーケンス を考えます2 1 4 3 6 5 8 7 10 9...。すべての要素は、その左隣または右隣の要素に関しては順不同ですが、他のすべての要素に関しては順不同です。したがって、各要素には一定数の反転があり、この場合は 1 です。このプロパティは、すべての要素が少し乱れる可能性があることを示しています。
バブル ソートと挿入ソートの両方が線形時間で実行されます。バブル ソートは、隣接する要素を交換し、確認のために別のパスを交換するため、順序を修正するのに 1 回のパスしかかかりません。挿入ソートは、要素ごとに 1 つの比較と交換のみを行う必要があります。
特性 2. この特性はより強力です。すべての要素を少し順不同にすることができることに加えて、いくつかの非常に順不同にすることができるようになりました。前と同じシーケンスを考えますが、最小の要素と最大の要素が反対側に移動します: n 2 4 3 6 5 8 7 10 9...1. Now1とnは、他のすべての要素に関して順不同です。
挿入ソートは引き続き線形時間で実行されます。前と同じように、ほとんどの要素は少数の比較とスワップのみを必要としますが、順序n比較とスワップを行うことができる要素がいくつかあります。この例では、最初のn-1要素はいくつかの比較とスワップ (OK、21 つだけ) を実行して配置し、最後の要素は比較とスワップを実行しますn-1--2*(n-1) + 1*(n-1)は ordernです。
この例では、バブル ソートは非常に困難です。各パススルーは1、1 ステップだけ後方に移動できます。したがって、少なくとも完了前に比較が行われる(n-1)パスが必要です。これは乗法です。(逆方向にバブル ソートを実行することもできます。その場合、最初の最大の要素が反対側の端にゆっくりと移動します。)(n-1)(n-1)*(n-1)n^2