バブル ソートの利点と欠点

PC や Web 開発からモバイル デバイスや組み込みシステムのコーディングに切り替えるプログラマーは、独自のデータ構造とアルゴリズムの選択とコーディングにより多くの時間を費やすことに気付きます。メモリが少なく、データ ストレージが限られているため、ビルド済みのライブラリやフレームワークを配置する余地はありません。そのため、独自のソート ルーチンを作成する必要がある人のために、低度のバブル ソートを選択する際の考慮事項をいくつか示します。

​​ 背景

バブル ソートは、メモリ内の項目のリストを並べ替える単純なアルゴリズムです。配列を指定すると、コードは隣接する項目の各ペアを繰り返し比較し、順序が正しくない場合はそれらを交換します。このプロセスは、スワップが発生しなくなるまで繰り返されます。並べ替えの進行中に配列を表示できた場合、低い値は一番上に「バブル」し、大きい値は一番下に沈みます。 Visual Basic 2010 の関連コードは次のとおりです:

while swap =True swap =False For i =0 To tbl.length - 2 If tbl(i)> tbl(i + 1) Then tmp =tbl(i) tbl(i) =tbl(i + 1) tbl(i + 1) =tmp swap =True End If Next End While

バブル ソートを選択するタイミング

このアルゴリズムにはいくつかの利点があります。書きやすく、理解しやすく、数行のコードしか必要としません。データは所定の場所に並べ替えられるため、メモリのオーバーヘッドはほとんどなく、並べ替えが完了すると、データはメモリ内にあり、処理の準備が整います。主な欠点は、ソートに時間がかかることです。テーブル要素の数が増えると、平均時間はほぼ指数関数的に増加します。アイテム数が 10 倍になると、並べ替えに約 100 倍の時間がかかります。

その他の配列ソート

並べ替えアルゴリズムは、複雑さ、速度、およびオーバーヘッドが異なります。バブル ソートは最も複雑ではありませんが、最も遅いものの 1 つでもあります。挿入ソートや交換ソートなどのその他の配列ベースのソートは、少し高速ですが、より多くのコードを必要とします (以下の参照を参照)。配列ベースの並べ替えの主な利点は、使用するコードが最小であり、使用する作業メモリの量が最小であることです。項目数が数百未満の単純な配列については、これらの並べ替えを検討してください。

複雑なソート アルゴリズム

データ セットが大きいほど、より複雑なコードとより多くのメモリが必要になります。クイック ソートとヒープ ソートは、データ セットの分割とコピーの両方を行い、比較の数を最適化します。クイック ソートでは、リストが継続的に分割され、ソートされた順序で再構築されます。ヒープソートは、データをツリー構造にコピーしてから、ツリーをトラバースしてデータを元の順序にコピーします。どちらも高速で効率的ですが、より多くのコードとより多くの作業用ストレージを必要とします。大規模なデータセットにはこれらのアルゴリズムを選択してください。