ゆめさくエンジニア研究所女性向けエンジニアスクール女性向けエンジニアスクール
ログイン

バブルソートと挿入・選択ソート

回 2-2　道 2 データ構造とアルゴリズム

バブルソートは、隣どうしの 2 つを比べて逆の順なら入れ替え、これを端までくり返して大きい値から順に右端へ送る並べ方です。n 個を並べると比べる回数は最大で n(n − 1) / 2 回で、10 個なら 45 回、100 個なら 4950 回です。データが 2 倍になると回数は約 4 倍になり、挿入ソートと選択ソートも同じ増え方をします。

目安 50 分2-2 (2-0〜2-10 の中)

読み終えたらデータが 2 倍で比べる回数が約 4 倍になることを、測った数で示せる

この頁の流れ

  1. 1背の順に並べる手順を、どう書けばよいか
  2. 2バブルソート、選択ソート、挿入ソートはどう動くのか
  3. 3動かして確かめる
  4. 4遅いソートはどこで崩れるのか
  5. 5遅いソートは仕事でどう確かめるのか
  6. 6関わる実例
  7. 7よくある問い
  8. 8確認クイズ
  9. 9説明課題
  10. 10もっと深く
  11. 11一次資料
  12. 12次へ

3 つの遅いソートを、比べる回数、入れ替える回数、並び方への強さ、同じ値の順を守るかで見分けられるようになります。

文 ゆめさくコード編集部公開 2026年10月26日更新 2026年10月26日出典を確かめた日 2026年10月26日

背の順に並べる手順を、どう書けばよいか

背の順に並べる手順は、隣どうしを比べて入れ替える、残りから一番小さい人を選ぶ、1 人ずつ正しい所に差し込む、の 3 通りで書けます。それぞれがバブルソート、選択ソート、挿入ソートです。

体育の時間に、ばらばらに並んだ 30 人を背の順に並べるとします。先生が全員を一度に見渡せないなら、決まった手順をくり返すしかありません。

どの手順でも、最後には正しく並びます。違うのは、比べる回数と、人を動かす回数です。人数が 2 倍になったとき、手間は何倍になるでしょうか。

この回では、3 つの並べ方 (ソート) で、比べた回数と動かした回数を実際に数えます。どれもデータが 2 倍になると比べる回数が約 4 倍になるので、まとめて遅いソートと呼びます。

バブルソート、選択ソート、挿入ソートはどう動くのか

3 つとも、まだ並んでいない部分から 1 つずつ正しい位置を決めていく手順で、決め方だけが違います。

バブルソートは隣どうしを比べて入れ替える

バブルソートは、左から順に隣の 2 つを比べ、左が大きければ入れ替えます。端まで進むと、一番大きい値が右端に着きます。泡 (バブル) が水面に浮かぶように大きい値が上がっていくので、この名前です。

4 つの数 [5, 3, 8, 2] で 1 周目を追うと、次の通りです。

  1. 5 と 3 を比べ、逆なので入れ替えて [3, 5, 8, 2]
  2. 5 と 8 を比べ、順なのでそのまま
  3. 8 と 2 を比べ、逆なので入れ替えて [3, 5, 2, 8]。8 が右端に着く

2 周目は右端の 8 を除いた 3 つで、3 周目は 2 つで同じことをします。比べる回数は 3 + 2 + 1 = 6 回です。n 個なら (n − 1) + (n − 2) + … + 1 で、n(n − 1) / 2 回になります。

1 周のあいだに 1 回も入れ替えなければ、もう並んでいるので、そこで止められます。この頁のコードは、この止め方を入れたバブルソートです。

バブルソート

選択ソートは残りから一番小さい値を選ぶ

選択ソートは、まだ並んでいない部分を全部見て一番小さい値を選び、その部分の先頭と入れ替えます。先頭から 1 つずつ確定していきます。

一番小さい値を選ぶには、残りの全部を見るしかありません。そのため、データがどんな並びでも、比べる回数は必ず n(n − 1) / 2 回です。その代わり、入れ替えるのは 1 周に 1 回までなので、入れ替えの回数は最大でも n − 1 回で済みます。

比較は同じ、交換だけが違う

挿入ソートは 1 つずつ正しい所に差し込む

挿入ソートは、左側を並んだ状態に保ち、右から 1 つ取って、左側の正しい位置まで大きい値を右へずらして差し込みます。トランプの手札を並べるときのやり方です。

差し込む値より小さい値に出会ったら、そこで止まります。ですから、もともと並んでいるデータでは、1 つにつき 1 回比べるだけで済み、n − 1 回で終わります。逆の順に並んだデータが最悪で、n(n − 1) / 2 回です。

乱れの数だけ手数が増える

3 つの違いを表で比べる

見る所バブル選択挿入
比べる回数 (最悪)n(n−1)/2n(n−1)/2n(n−1)/2
並んだデータn − 1n(n−1)/2n − 1
入れ替え (最悪)n(n−1)/2n − 1n(n−1)/2
同じ値の順守る崩す守る
計算量O(n²)O(n²)O(n²)

バブルと挿入の「並んだデータ」の n − 1 回は、バブルは止め方を入れた場合、挿入はもともとの手順の場合です。挿入ソートの「入れ替え」は、右へずらした回数です。計算量 (データが増えたときの手間の増え方) は 3 つとも O(n²) で、データが 2 倍なら比べる回数は約 4 倍になります。表の回数は、下のコードの出力で確かめます。

動かして確かめる

1 本目は、100 件、200 件、400 件のばらばらの数を、3 つのソートで並べます。出力の 1 つ目のまとまりは比べた回数、2 つ目は件数を 2 倍にしたときの倍率、3 つ目はバブルと選択が入れ替えた回数と、挿入が右へずらした回数です。左から、バブル、選択、挿入の順です。並びは、乱数の代わりに決まった式で混ぜているので、誰が動かしても同じになります。

動かす 3 つのソートの回数を数える

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

件数 バブル 選択 挿入
100 4944 4950 2705
200 19834 19900 9975
400 79745 79800 43712
2 倍にしたときの倍率
100 → 200 4.01 4.02 3.69
200 → 400 4.02 4.01 4.38
入れ替え、ずらした回数
100 2610 92 2610
200 9779 193 9779
400 43317 395 43317

比べた回数は、100 件でバブル 4944 回、選択 4950 回、挿入 2705 回です。選択の 4950 は 100 × 99 / 2 の通りです。バブルは最後の数周で入れ替えが無くなって止まったので、4950 より 6 回少なくなりました。

件数を 2 倍にすると、バブルと選択は 4.01 倍や 4.02 倍で、ほぼちょうど 4 倍です。挿入は 3.69 倍と 4.38 倍で、データの乱れ具合によって揺れますが、2 回の倍率を掛けると 4 倍を 2 回掛けた 16 倍の近くになります。どれも、データが 2 倍で比べる回数が約 4 倍の、n² の形です。

3 つ目のまとまりでは、バブルが入れ替えた回数と、挿入がずらした回数が、どの件数でも同じです (100 件で 2610 回)。どちらも、順が逆になっている 2 つの組 (乱れ) を 1 つずつ直すたびに 1 回動かすからです。選択は 92 回しか入れ替えていません。

2 本目は、100 件で、並んだデータ、2 か所だけ入れ替えたほぼ並んだデータ、逆の順のデータを比べます。出力は比べた回数です。

動かす 並び方で回数が変わる

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

並んだ
 バブル 99
 選択   4950
 挿入   99
ほぼ並んだ
 バブル 197
 選択   4950
 挿入   101
逆順
 バブル 4950
 選択   4950
 挿入   4950

並んだデータでは、バブルと挿入は 99 回で終わり、選択は 4950 回かかります。ほぼ並んだデータでは、挿入は 101 回、バブルは 197 回です。逆の順は、3 つとも 4950 回で最悪です。

ほとんど並んでいるデータに 1 件足して並べ直す、という場面では、挿入ソートがとても少ない回数で済みます。

遅いソートはどこで崩れるのか

遅いソートは、データが多いと回数が 2 乗で増えること、選択ソートは同じ値の順を崩すこと、の 2 つで困ります。

件数が 10 倍で、回数は 100 倍

選択ソートの比べる回数 n(n − 1) / 2 に、件数を入れて並べます。

動かす 件数が増えると比べる回数は

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

     10 件            45 回
    100 件         4,950 回
  1,000 件       499,500 回
 10,000 件    49,995,000 回
100,000 件 4,999,950,000 回

10 件で 45 回だったのが、1,000 件で 499,500 回、100,000 件では 4,999,950,000 回です。件数が 10 倍になるたびに、回数はほぼ 100 倍になります。会員 10 万人の名簿を選択ソートで並べると、約 50 億回比べることになります。

次の回 2-3 で学ぶマージソートとクイックソートは、半分に分けて並べるので、データが 2 倍になっても比べる回数は 2 倍と少ししか増えません。件数が多いほど、遅いソートとの差は大きく開きます。

同じ点数の人の順が入れ替わる

並べる前の順のうち、同じ値どうしの順を守るソートを、安定なソートと呼びます。バブルソートと挿入ソートは安定で、選択ソートは安定ではありません。

次のコードは、受付の順に並んだ 3 人を、点数だけで小さい順に並べます。青木さんと伊藤さんは同じ 2 点で、受付は青木さんが先です。

動かす 同じ点数の順が入れ替わる

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

選択
  1 上田
  2 伊藤
  2 青木
挿入
  1 上田
  2 青木
  2 伊藤

挿入ソートでは、青木さん、伊藤さんの順が残ります。選択ソートでは、伊藤さん、青木さんの順に入れ替わりました。最初の周で、一番小さい上田さんを先頭の青木さんと入れ替えたとき、青木さんが伊藤さんより後ろへ飛んだからです。

「受付の順に並べたあと、点数で並べ直す」のように、2 回に分けて並べる処理では、安定でないソートを使うと 1 回目の順が崩れます。Python の公式文書は、Python のソートは安定だと保証しています。

遅いソートは仕事でどう確かめるのか

仕事では、遅いソートを自分で書くより、言語の sorted や sort を使い、手で書いた並べ替えやループの中に n² の形が隠れていないかを確かめます。

  1. 並べ替えには言語の道具を使う。Python のソートは、公式文書によると安定で、すでにある並びを生かして速く並べる
  2. 自分で書いた並べ替えは、sorted の結果と照らす試験を書く。並んだ、逆の順、同じ値が混じる、0 件、1 件の 5 つの並びは必ず試す
  3. ループの中で、毎回リストの全部を見ている所を探す。並べ替えでなくても、全部と全部を比べていれば、バブルソートと同じ n(n − 1) / 2 の形になる
  4. 件数を 2 倍にして、回数か時間が約 4 倍になったら、n² の形を疑う

遅いソートも、実務のソートの中で使われています。Python のソートの説明書 (CPython の listsort.txt) によると、Python のソートは、短い列は二分挿入ソート (差し込む位置を二分探索で探す挿入ソート) で並べ、長い列も、短い区切りを二分挿入ソートで伸ばしてからマージします。少ない件数では、手順が単純な挿入ソートの方が速いからです。

試験で sorted と照らす

def test_matches_sorted():
    cases = [[], [1], [1, 2],
             [2, 1], [2, 1, 2]]
    for a in cases:
        got = my_sort(a)
        assert got == sorted(a)

関わる実例

GTA Online の読み込みが 6 分かかった (2021年2月28日)

2021年2月28日、ゲーム GTA Online の読み込みの遅さを自分で調べた人が、ブログで原因を公表しました。オンラインの読み込みに約 6 分かかり、その間 CPU の 1 つのコアが使い切られていました。

原因は 2 つありました。1 つは約 10MB の JSON (データを文字で書く形式) を読む処理の遅さです。もう 1 つは、約 63,000 件の品物を読み込むとき、1 件入れるたびに、それまでに入れた全部と 1 件ずつ比べて重複を確かめていたことです。書き手は、この比べる回数を (n² + n) / 2 として約 19 億 8 千万回と見積もっています。しかも、入れる品物はもともと重複していませんでした。

書き手が 2 つを直すと、読み込みは 1 分 50 秒になり、約 69.4% 短くなりました。重複の確かめだけを直した場合でも、6 分から 4 分 30 秒に縮んでいます。書き手は2021年3月15日にゲームの会社から報奨金を受け取り、3月16日には会社が直した版を出したと追記しています。

崩れた前提は「1 件入れるときに全部を確かめても大した手間ではない」です。1 件ずつなら軽くても、全部の件数でくり返すと、バブルソートや選択ソートと同じ n² の形になります。書き手は、重複の確かめにハッシュ表を使うか、起動時の確かめを省くことを勧めています。

出典は How I cut GTA Online loading times by 70% (t0st のブログ、英語) です。

よくある問い

バブルソートの比較回数は何回ですか

n 個を並べるとき、最大で n(n − 1) / 2 回です。4 個なら 6 回、10 個なら 45 回、100 個なら 4950 回です。1 周で入れ替えが無ければ止める書き方なら、並んだデータでは n − 1 回で終わります。

バブルソートの計算量はいくつですか

最悪と平均は O(n²) で、データが 2 倍になると比べる回数は約 4 倍になります。上の 1 本目のコードでは、100 件から 200 件で 4.01 倍でした。止め方を入れれば、並んだデータでは O(n) で済みます。

バブルソートは安定ですか

安定です。隣どうしで、左が右より大きいときだけ入れ替えるので、同じ値どうしは入れ替わらず、もとの順が残ります。挿入ソートも安定で、選択ソートは離れた位置と入れ替えるので安定ではありません。

バブルソートは実務で使われますか

そのままの形で使うことはほとんどなく、言語の sorted や sort を使います。ただ、同じ遅いソートの仲間の挿入ソートは、Python のソートが短い区切りを並べるときに使っています。JavaScript の V8 も、公式ブログによると、v7.0 で今の並べ方に替える前は、10 個より短い配列を挿入ソートで並べていました。

3 つのうち、どれを覚えればよいですか

1 つ選ぶなら挿入ソートです。ほとんど並んだデータに強く、安定で、実務のソートの中でも使われています。バブルソートは手順が一番やさしいので、並べ替えの考え方の入口として学ぶ価値があります。

確認クイズ

答えだと思う選択肢を押すと、その場で正誤と理由が開きます。4 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。

1 問目

ばらばらのデータで、件数を 100 件から 200 件に増やしました。バブルソートで比べる回数は、だいたい何倍になりますか。

2 問目

100 件のうち 2 か所だけ順が入れ替わっている、ほぼ並んだデータがあります。比べる回数が一番少ないのはどれですか。

3 問目

受付の順に並んだ名簿を、点数で並べ直します。同じ点数の人は受付の順のまま残したいとき、使ってはいけないのはどれですか。

4 問目

このコードを動かすと何が出ますか。早く終える工夫を入れていないバブルソートで、比べた回数 cmp と入れ替えた回数 swp を数えます。

比べた回数と入れ替えた回数

a = [2, 1, 4, 3]
cmp = swp = 0
n = len(a)
for e in range(n-1, 0, -1):
    for i in range(e):
        cmp += 1
        if a[i] > a[i+1]:
            t = a[i+1]
            a[i+1] = a[i]
            a[i] = t
            swp += 1
print(cmp, swp)

説明課題

上の 1 本目のコードの出力を使って、データが 2 倍になると比べる回数が約 4 倍になることを示してください。100 件と 200 件の回数、その倍率、なぜ 4 倍になるのかを、3 文以内で書いてください。書いたら、下の模範解答を開いて比べてください。

模範解答

自分の説明を書いてから開いて、比べてください。

この回の先の一歩

件数が増えたとたんに画面や集計が遅くなる原因は、2 乗で増える比べ方であることがよくあります。回数を数えて増え方を示せると、遅さの相談に数で答えられます。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。

もっと深く

この回の続きを、ゆめさくのコースの章や道具で深められます。頁の中の確認クイズに答えたあと、手を動かす量を増やしたいときに使ってください。

一次資料

どれも 2026年10月26日に開いて、題と中身を確かめました。

次へ

前の回 2-1線形探索と二分探索100 万件でも 20 回で見つかる次の回 2-3クイックソートとマージソート速いソート 2 つ、平均と最悪

道 2 データ構造とアルゴリズムの回

  1. 2-0アルゴリズムとは順次、分岐、反復の 3 つで書く手順頁で読む
  2. 2-1線形探索と二分探索100 万件でも 20 回で見つかる頁で読む
  3. 2-2バブルソートと挿入・選択ソート遅いソート 3 つ、2 倍で約 4 倍この回
  4. 2-3クイックソートとマージソート速いソート 2 つ、平均と最悪頁で読む
  5. 2-4スタックとキュー積む順と並ぶ順頁で読む
  6. 2-5再帰自分を呼んで小さくする頁で読む
  7. 2-6木と二分探索木たどる順、片寄り頁で読む
  8. 2-7ハッシュテーブル鍵から一気に引く、衝突頁で読む
  9. 2-8ダイクストラ法と最短経路点と線、幅優先、重みのある道頁で読む
  10. 2-9動的計画法同じ計算を 2 度しない頁で読む
  11. 2-10試験と面接で確かめる基本情報 科目B、道場 10 問、面接 20 問頁で読む

道 2 の頁へ戻るほかの道を見る