- 比較中
- 交換済み
- 確定
バブルソート
バブルソートはリストを何度もたどり、隣り合う値を比較して、左の方が大きければ交換します。パスのたびに、まだ位置が決まっていない最大の値が泡のように末尾へ浮かび上がります。好きな速度で再生するか、比較を1回ずつ進めながら、比較・交換・パスのカウンターを確認しましょう。 「再生」で並べ替えを見るか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。タイルには比較回数、交換回数、パス数が表示されます。棒の数や初期の並びを選ぶか、数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 棒の数と初期の並びを選びます:ランダム、ほぼ整列済み、逆順、重複が多い。数値を自分で入力することもできます。
- 「再生」を押すか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると、並べ替えの好きな位置に移動できます。
- タイルの比較回数、交換回数、パス数を見て、最悪の場合と比べてみましょう。
バブルソートの仕組み
左端から始めます。最初の2つの値を比較し、左の方が大きければ交換します。1つ右へ進んでまた比較し、リストの最後まで続けます。これが1回のパスで、最大の値が最後の位置に来ます。次のパスは1つ手前で終わります。交換のないパスが出るか、値が1つだけ残るまで繰り返します。
手間を数える
n個の値では、最初のパスでn − 1回、次のパスでn − 2回と比較していくので、全体の比較回数は最大でn(n − 1)/2回です。交換回数は常に初期リストの転倒数、つまり順序が逆になっている値のペアの数と同じです。逆順のリストが最も多く、n(n − 1)/2個です。整列済みのリストには転倒がなく、早期終了があればn − 1回の比較、1パスで終わります。
よくある質問
なぜバブルソートと呼ぶのですか?
大きな値が水中の泡のようにリストの末尾へ浮かび上がるからです。各パスで、まだ位置が決まっていない最大の値が1つずつ右へ動き、最終位置に着きます。
バブルソートの比較と交換は何回ですか?
n個の値で比較は最大n(n − 1)/2回です。10個なら45回、40個なら780回です。交換回数は常に初期リストの転倒数と等しく、整列済みなら0回、逆順ならn(n − 1)/2回です。
早期終了とは何ですか?
1回のパス全体で交換がなければ、隣り合う値はすべて正しい順序なので、リストは整列済みで処理を終えられます。早期終了をオンにすると、整列済みのリストは1パスで終わります。オフにすると、バブルソートは常にn − 1回のパスをすべて行います。
バブルソートは実際に使われますか?
ほとんど使われません。単純で安定ですが、平均でn²に比例する時間がかかります。短いリストやほぼ整列済みのリストでは挿入ソートの方が少ない手順で済み、長いリストではマージソートやクイックソートの方がはるかに高速です。
入力した数値はどこかに送信されますか?
いいえ。並べ替えはブラウザ内で実行され、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ