バブルソート
リストを端から端まで何度も見ていき、順番が逆の隣同士を入れ替えます。1周するたびに、残りの最大値が右端に来ます。
- 最良 Ω(n)
- 平均 Θ(n²)
- 最悪 O(n²)
- メモリ O(1)
- 安定
- 追加メモリ不要
用語の意味
- 最良: この方法にとって一番楽な入力のとき、リストのサイズ n に応じて時間がどう増えるか。
- 平均: ふつうの場合に、n に応じて時間がどう増えるか。n² なら値の数が2倍で時間は約4倍。n log n はずっとゆっくり増えます。
- 最悪: 一番難しい入力での増え方。速さが決して落ちてはいけないときに役立ちます。
- メモリ: リストのほかに必要な追加メモリの量。1 なら変数がいくつかだけ、n ならリストのコピー1つ分です。
- 安定: 同じ値どうしが元の順番を保ちます。レコードを1つの項目で並べ替えるときに大切です。
- 追加メモリ不要: 2つ目のリストを使わず、リストそのものの中で並べ替えます。
- 比較中
- 移動中
- 位置が確定
比較回数 入れ替え回数
再生を押すと、並べ替えが進むにつれてコストが増える様子を線で表示します
再生を押すか、1ステップずつ進めてください。
スペースキー: 再生・一時停止。左右の矢印キー: ステップ移動。Home キーと End キー: ジャンプ。
試してみましょう: ほぼ並んでいるリストを選んでください。入れ替えのない周が1回あれば、そこで早めに終わります。
仕組み
隣り合う2つの値を比べ、左の方が大きければ入れ替えます。すると1周ごとに最大値が、泡が浮かぶように右端まで進みます。入れ替えが1回もない周があれば、リストはもう並んでいます。
向いている場面
長いリストでは遅いので、実際のプログラムではほとんど使いません。ただし学ぶには最適です。比べて入れ替えるという、並べ替えの基本がよくわかります。速いのは、リストが最初から並んでいるときだけです。