1. 概要

このチュートリアルでは、バブルソートアルゴリズムについて説明します。アルゴリズムの擬似コードを示し、その時間計算量を分析します。

2. アルゴリズム

バブルソートは、シンクソートとも呼ばれ、配列内の要素をソートするための非常に単純なアルゴリズムです。 バブルソートは、元の入力リストに間違った順序で表示されている場合、隣接する要素を継続的に交換することで機能します。 このスワッピングプロセスは、入力リストを並べ替えるまで続きます。

このセクションでは、バブルソートの手順について詳しく説明します。

まず、バブルソートアルゴリズムの擬似コードを見てみましょう。

次に、このアルゴリズムで使用される手順と表記法について説明します。 目標は、入力配列を取得し、その要素を昇順で並べ替えることであることに注意してください。

最初の要素（配列内のインデックス）から始めます。 次に、配列内の次の要素（のインデックス）が現在の要素よりも大きいかどうかを確認します。 現在の要素（配列のインデックス）が次の要素（のインデックス）よりも大きい場合は、それらを交換します。 現在の要素が次の要素よりも小さい場合は、配列内の次の要素に移動します。

このようにして、アレイ全体のスワップを処理して完了します。 これは最初の反復です。

必要な反復回数は、配列内の要素の数と同じです。 必要な反復が終了したら、配列を昇順で並べ替えます。 ただし、バブルソートでは昇順と降順の両方で並べ替えることができることに注意してください。

上記のバブルソートでは、いくつかの問題があります。 このバージョンでは、可能なスワッピングについて要素のすべてのペアを比較します。 必要な反復が完了するまでこれを続けます。

ここで、指定された入力配列がほぼまたはすでにソートされていると仮定しましょう。 残念ながら、現在の擬似コードでは、配列が並べ替えられていることを示すインジケーターがないため、すべての反復を実行します。 これを改善できますか？見てみましょう。

各反復の後、交換する要素を追跡しましょう。 スワップがない場合は、入力配列をソートしたと見なすことができます。

この仮定により、改善されたバブルソートアルゴリズムを提示する準備が整いました。

このアルゴリズムでは、スワップされる要素を追跡するための新しい変数を導入しました。 また、これは、指定された配列が反復中にすでにソートされているかどうかを示すことができます。 したがって、反復中のある時点で、アレイ全体でスワップが発生しなければ、ループから抜け出し、それ以上の反復は必要ありません。

3. 時間計算量分析

3.1. 標準的なバブルソートの時間計算量

バブルソートの標準バージョンの場合、反復を行う必要があります。 各反復で比較を行い、必要に応じてスワッピングを実行します。 サイズの配列が与えられると、最初の反復で比較が実行されます。 2回目の反復では、比較が実行されます。 このように、比較の総数は次のようになります。

したがって、の場合、標準のバブルソートの時間計算量はになります。

それでは、バブルソートのベストケースとワーストケースについて話しましょう。 最良のケースは、入力配列がすでにソートされている場合です。 この場合、すべての要素をチェックして、スワップの必要があるかどうかを確認します。 それでもスワッピングがない場合は、反復を続行して完了します。 したがって、最良のシナリオでは、標準のバブルソートの時間計算量はになります。

ワーストケースでは、配列は逆にソートされます。 したがって、最初の反復、2番目の相互作用などで比較を行う必要があります。 したがって、最悪の場合のバブルソートの時間計算量は、平均的な場合と最良の場合と同じになります：。

3.2. 改善されたバブルソートの時間計算量

バブルソートが改善された場合、標準バージョンと比較して実行する必要のあるスワップが少なくなります。 時間計算量について言えば、平均および最悪の場合の時間計算量は、標準のと同じになります。 平均的および最悪の場合、改善されたバージョンの効率とパフォーマンスに改善がありますが。

最良の場合、指定された配列がすでにソートされている場合、改良されたバブルソートにより、標準バージョンと比較して時間計算量が向上します。

この場合、配列が与えられると、可能なスワップを探してリストをトラバースします。 ただし、配列はすでにソートされているため、スワップはありません。 ここでは、反復をこれ以上続行しません。 代わりに、ループから抜け出し、アルゴリズムが終了します。 このように、すべての反復を完了する必要はありません。

指定された配列がソートされている場合、配列を1回トラバースします。 したがって、最良の場合の時間計算量はになります。

4. 実装

実際のバブルソートを確認するには、Javaでのバブルソートの実装に関するの記事を参照してください。

5. 長所と短所

バブルソートは、理解して実装するための非常に単純なソートアルゴリズムです。 その単純さのために、バブルソートはコンピュータサイエンスにソートアルゴリズムを導入するために使用されます。 また、他の人気のある並べ替えアルゴリズムの優れた基盤を提供します。 入力配列がほぼソートされていて、いくつかの要素を交換する必要がある場合は、バブルソートが適切なオプションです。 また、安定ソートアルゴリズムであり、ポリゴン充填アルゴリズムはバブルソートの概念を使用しています。

バブルソートの主な欠点は、時間の複雑さです。 入力配列に多数の要素が含まれている場合、バブルソートの効率は劇的に低下し、平均時間は2乗で増加します。 最新のCPUハードウェアでのバブルソートのパフォーマンスは非常に劣っています。 バブルソートの実行時間は漸近的に同等であり、挿入ソートなどの他の一般的なソートアルゴリズムと同等ですが、バブルソートは要素間で非常に多くのスワップを実行します。

6. 結論

このチュートリアルでは、バブルソートについて説明しました。 バブルソートアルゴリズムの標準バージョンと改良バージョンを紹介しました。

さらに、両方のバージョンの時間計算量の詳細な分析を示しました。