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

2019

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

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

比較表

比較基準	バブルソート	選択ソート
基本	隣接する要素が比較されて入れ替えられます	最大の要素が選択され、最後の要素と交換されます（昇順の場合）。
ベストケースの時間の複雑さ	に）	O（n `2` ）
効率	非効率的な	バブルソートと比較して効率が向上
安定している	はい	いいえ
方法	交換	選択
速度	スロー	バブルソートと比較して速い

バブルソートの定義

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

このアルゴリズムは最も遅いソートアルゴリズムです。バブルソートの最善の場合の複雑度（リストが正しい順序のとき）は、次数n（ O（n） ）であり、最悪の場合の複雑度はO（n 2）です。最良の場合、要素を比較するだけで、要素を入れ替えることはないので、n次です。この手法では、一時変数を格納するための追加のスペースも必要です。

選択ソートの定義

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

選択ソートでは、ソートされソートされていない配列は何の違いもなく、ベストケースとワーストケースの両方の複雑さでn2（ O（n2） ）のオーダーを消費します。選択ソートはバブルソートよりも高速です。

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

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