バブルソートと選択ソートの違い

コンテンツ

比較表
バブルソートの定義
選択ソートの定義
結論

ソートは、配列の要素が特定の順序で配置されるコンピュータープログラムの主要なタスクの1つです。並べ替えにより、検索が簡単になります。バブルソートと選択ソートは、ソートに使用する方法によって区別できるソートアルゴリズムです。基本的にバブルソートは要素を交換しますが、選択ソートは要素を選択してソートを実行します。

2つの間のもう1つの大きな違いは、バブルソートは安定したアルゴリズムであり、選択ソートは不安定なアルゴリズムであることです。アルゴリズムは、リストまたは配列でソートする前に発生していたのと同じ順序で発生する同じキーを持つ要素が安定していると見なされます。一般に、ほとんどの安定した高速アルゴリズムは追加のメモリを使用します。

比較表
定義
主な違い
結論

比較表


比較の根拠	バブルソート	選択ソート
ベーシック	隣接する要素が比較され、交換されます	最大の要素が選択され、最後の要素と交換されます（昇順の場合）。
最適な時間の複雑さ	に）	に`²`)
効率	非効率的な	バブルソートと比較して効率が向上
安定した	はい	いや
方法	交換	選択
速度	スロー	バブルソートと比較して高速

バブルソートの定義

バブルソート は、各アイテムまたは要素をその隣のアイテムと比較し、必要に応じてそれらを交換することにより動作する最も単純な反復アルゴリズムです。簡単に言えば、リストの最初の要素と2番目の要素を比較し、特定の順序になっていない限りそれを交換します。同様に、2番目と3番目の要素が比較および交換され、この比較と交換がリストの最後まで続きます。最初の反復での比較の数はn-1で、nは配列の要素数です。最初の反復の後、最大の要素はn番目の位置になります。そして、各反復の後、比較の数は減少し、最後の反復では1つの比較のみが行われます。

このアルゴリズムは、最も遅いソートアルゴリズムです。バブルソートの最適な複雑さ（リストが順序どおりの場合）の順序はn（に））、最悪の場合の複雑さは に²)。最良の場合、要素を比較するだけで、それらを交換しないため、n次です。この手法では、一時変数を格納するための追加スペースも必要です。

選択ソートの定義

選択ソート バブルソートアルゴリズムよりもわずかに優れたパフォーマンスを達成し、効率的です。配列を昇順で並べ、最大の要素を見つけて最後の要素と交換することで機能し、リスト全体が並べ替えられるまでサブ配列で次のプロセスを繰り返したいとします。

選択ソートでは、ソートされた配列とソートされていない配列に違いはなく、nのオーダーを消費します² (に²)）最良の場合と最悪の場合の両方の複雑さ。選択ソートは、バブルソートよりも高速です。

バブルソートでは、各要素とその隣接要素が比較され、必要に応じて交換されます。一方、選択ソートは、要素を選択し、その特定の要素を最後の要素と交換することにより機能します。選択された要素は、昇順または降順など、順序に応じて最大または最小になります。
最悪の場合の複雑さは、両方のアルゴリズムで同じです。つまり、O（n²）、しかし最高の複雑さは異なります。バブルソートはn時間のオーダーを要するのに対し、選択ソートはnのオーダーを消費します² 時間。
バブルソートは安定したアルゴリズムですが、対照的に、選択ソートは不安定です。
選択ソートアルゴリズムは、非常に遅くて非効率的なバブルソートと比較して、高速で効率的です。