バブルソートと挿入ソートの主な違いは、バブルソートが隣接するデータ要素を確認し、順序が間違っていれば入れ替えることでソートを行うのに対し、挿入ソートは部分的にソートされた配列に1要素ずつ転送することでソートを行う点です。
アルゴリズムとは、ある問題を解決するための一連の手順です。
ソートはデータセットに対して行われる一般的な操作です。
データセットのソートには様々なアルゴリズムがあります。
そのうちの2つはバブルソートと挿入ソートです。
また、この2つのアルゴリズムは単純なソートアルゴリズムとみなされている。
バブルソートとは
バブルソートは、最も単純なソートアルゴリズムです。
隣接するペアを一度に比較することにより、要素をソートします。
次のような例を考えてみよう。
40 30 10 70 50 20 60
バブルソートでは、隣接する要素を比較する。
まず、40と30を考える。
30 は 40 よりも小さい。
そこで、この2つの数字を入れ替えることができる。
30 40 10 70 50 20 60
次に、40と10を考えます。
10は40より小さい。
そこで、この2つの数字を入れ替えることができる。
30 10 40 70 50 20 60
次に、40と70を考えてみましょう。
70は40より大きいので、数字を入れ替える必要はない。
次に、70と50を考えてみます。
50は70より小さい。
50は70より小さいので、この2つの数字を入れ替えることができます。
30 10 40 50 70 20 60
次に、70と20を考えます。
20は70より小さいので、この2つの要素を入れ替えることができます。
30 10 40 50 20 70 60
次に、70と60を考えます。
60 は 70 よりも小さい。
したがって、この2つの数字を入れ替えなければなりません。
30 10 40 50 20 60 70
さて、データセットの中で最大の要素が最後になったことがわかると思います。
つまり、1回目のパスの終了時に、最大の要素はすでにソートされているのです。
したがって、次回は70はすでにソートされているので、考慮する必要はありません。
他の6つの要素をチェックすればよいのです。
さらに、一度に2つの要素を比較する必要があります。
30と10を考えてみましょう。
10は30より小さい。
10は30より小さいので、この2つの数字を入れ替える。
10 30 40 50 20 60 70
次に、30と40を考える。
40は30より大きい。
40は30より大きいので、数字を入れ替える必要はない。
次に、40と50を考えてみましょう。
50は40より大きいので、入れ替えの必要はありません。
では、50と20を考えてみましょう。
20は50より小さい。
20は50より小さいので、この2つの数字を入れ替えます。
10 30 40 20 50 60 70
では、50と60を考えてみましょう。
入れ替えは必要ありません。
2回目のパスの最後には、2番目に大きい要素がソートされます。
つまり、60と70がソートされたことになる。
この処理は、すべての要素をソートするまで続けられます。
挿入ソートとは
挿入ソートのアルゴリズムは、部分的にソートされた配列に一度に1つの要素を転送することによってデータセットをソートします。
そのため、オーバーヘッドが小さい。
40 30 10 70 50 20 60
40を部分ソート配列とする。
30を部分配列とすると、40より小さくなってしまいます。
そこで、両者を入れ替えます。
30 40 10 70 50 20 60
ここで，10を考えます．10は30より小さいです。
そこで、以下のように要素を配置します。
10、30、40がソート済み配列になります。
10 30 40 70 50 20 60
ここで，70を考えます． 70は40より大きいので，移動する必要はありません．10, 30, 40, 70は部分的にソートされた配列の中にあります。
次に50を考えてみましょう。
70より小さいですが、40よりは大きいです。
正しい位置に配置することができます。
10, 30, 40, 50, 70 は部分的にソートされた配列になりました。
10 30 40 50 70 20 60
次に，20を考えてみましょう．これは10より大きく、20より小さいです。
これを正しい位置に配置することができます。
10,20,30,40,50,70 は部分的にソートされた配列の中にあります。
10 20 30 40 50 70 60
60を考えてみましょう。
70より小さく、50より大きい。
これを正しい位置に配置することができます。
10 20 30 40 50 60 70
これで、すべての要素がソートされたことがわかります。
ここで、挿入ソートにおける入れ替えの回数は最小になりますが、比較の回数はまだ多くなっています。
バブルソートと挿入ソートの違い
定義
バブルソートは単純なソートアルゴリズムで、リストを繰り返し見て、隣接するペアを比較し、順序が正しくない場合はそれらを交換します。
一方、挿入ソートは、一度に1つの要素を転送することによって最終的なソートリストを構築する単純なソートアルゴリズムです。
したがって、これがバブルソートと挿入ソートの主な違いです。
機能性
バブルソートが隣接する要素をチェックして入れ替えるのに対し、挿入ソートは部分的にソートされた配列に1つずつ要素を移します。
スワップ数
また、バブルソートと挿入ソートの重要な違いとして、スワップ回数が挙げられます。
挿入ソートはバブルソートに比べ、スワップ回数が少なくなっています。
速度
さらに、挿入ソートはバブルソートに比べて2倍の速さです。
複雑さ
バブルソートと挿入ソートのもう一つの違いは、挿入ソートがバブルソートよりも複雑であることである。
結論
バブルソートと挿入ソートは小さなデータセットをソートするのに適しています。
どちらも、クイックソートやマージソートなどの他の高度なソートアルゴリズムと比較すると、効率は落ちます。
バブルソートと挿入ソートの主な違いは、バブルソートが隣接するデータ要素をチェックし、順序が正しくない場合にそれらを交換することでソートを行うのに対し、挿入ソートは部分的にソートされた配列に一度に1つの要素を転送することでソートを行う点です。
