バブルソートと挿入ソートの違いは何ですか

NS 主な違い バブルソートと挿入ソートの間はバブルソートは、隣接するデータ要素をチェックし、順序が間違っている場合はそれらを交換することによってソートを実行しますが、挿入ソートは、一度に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未満です。したがって、これら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

これで、データセットの最大の要素が最後にあることがわかります。つまり、最初のパスの終了時に、最大の要素がすでに並べ替えられています。したがって、次回は70がすでにソートされているため、考慮する必要はありません。他の6つの要素をチェックするだけです。

10 30 40 50 20 60 70

ここで、30と40を検討します。40は30より大きいです。数値を交換する必要はありません。次に、40と50を検討できます。50は40より大きいため、交換する必要はありません。

ここで、50と20について考えます。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が部分的にソートされた配列にあると見なします。

30 40 10 70 50 20 60

ここで、10。10は30未満であると考えます。したがって、要素を次のように配置します。 10、30、および40は、部分的にソートされた配列にあります。

10 30 40 70 50 20 60

ここで、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つの違いは、挿入ソートはバブルソートよりも複雑なことです。

結論

バブルソートと挿入ソートは、小さなデータセットのソートに適しています。どちらも、クイックソートやマージソートなどの他の高度なソートアルゴリズムと比較すると、効率が低くなります。バブルソートと挿入ソートの主な違いは、バブルソートは隣接するデータ要素をチェックし、順序が間違っている場合はそれらを交換することでソートを実行するのに対し、挿入ソートは一度に1つの要素を部分的にソートされた配列に転送することでソートを実行することです。

参照：

1.「バブルソート」ウィキペディア、ウィキメディア財団、2019年4月15日、こちらから入手できます。 2.「挿入ソート」。ウィキペディア、ウィキメディア財団、2019年2月3日、こちらから入手できます。 3.「挿入ソートとは何ですか？ –Techopediaからの定義。」 Techopedia.com、こちらから入手できます。