【擬似言語⑫】バブルソート | アルゴのラスボス（基本情報技術者, 科目B, アルゴリズム）

このNoteでは、数値のソート（並替）アルゴリムの1種「バブルソート」の擬似言語を作ります。シリーズ後期の難しめNoteの知識を集約して乗り切ります。
＞【擬似言語⑪】ループの開始/終了ズラしNote
＞【擬似言語⑧】素数とフラグの決め打ちNote

処理を図解にして、配列の要素番号を書き出し、ループカウンタで制御する方針を決めて組み上げます。別解がたっっくさんありますよ。「これが正解」と覚えるのではなく、自分で組み上げる練習をして「これも正解？」と攻めた学習をして下さいね。

いよいよ擬似言語シリーズLv.2。ラスボスです！！

テキストの基礎を生かして、プログラム的な考察/工夫を学んでいきます。基礎と実用にギャップを感じる方のために作りました。
＞【FEB】擬似言語の教科書Note

ぜひ一緒に学習を進めていきましょう！

このNoteは、私がIT専門学校で授業したことを基に作成しています。IT専門学校でFEは第一目標として、カリキュラムが構築されています。何も知らずに入学しても、1年生10月にはFE合格していきますよ。実績ある教育ノウハウを詰め込んだので、少しでも信頼して頂けたら嬉しいです。

＞全Noteへのリンク（FE節）
※科目Aのテーマ別/科目B/旧FE午後など沢山作りました！

図解にして理解してから組む

複雑な処理=複雑な擬似言語なので、まずは図解に描き出して、処理内容を理解して、配列の添え字（要素番号）を書き出して、ループカウンタや数式を考えていきます。

まずは処理から。バブルソートは、隣同士を比較し続けて、一番大きい値を右端に追いやる処理を繰り返します。

1番大きい4が右端に到達したら、右端4は確定。つぎは2番目に大きい3を右端に追いやって確定。その次は2、という具合。

データは配列に入っていて、比較する要素を青/緑矢印で示しました。黒地は確定枠。

1巡目は①～③で全部比較して、右端4が確定。2巡目は④⑤で右端3が確定（4は確定なので、3は一歩左）。3巡目は⑥で2を確定させました。

他データで再度思考してみます。ちゃんと昇順（小さい順）に並ぶかな。

ループ回数やデータ数と絡めた立式

擬似言語に組み込むループ処理を考える準備。

要素番号の制御を考えます。1～3巡目で、比べる回数（位置）が少なくなってるのが分かります。

「i 巡目」の時、青矢印は「1から」「要素数 - i」まで1ずつ増やして比較してるって気づけば勝ち。

1巡目の時、青矢印は[1]から4-1=[3]まで。
2巡目の時、青矢印は[1]から4-2=[2]まで。
3巡目の時、青矢印は[1]から4-3=[1]まで。
必ず代入して正しいか確認してください。

○手続き名: bubbleSort(整数型の配列: array)
  整数型: i, j, swap, length
  
  length ← arrayの要素数
  
  for (i を 1 から length-1 まで 1 ずつ増やす)
    for (j を 1 から length-i まで 1 ずつ増やす)
      if (array[j] > array[j + 1])
        swap ← array[j]
        array[j] ← array[j + 1]
        array[j + 1] ← swap
      endif
    endfor
  endfor

内側「j」ループは、隣比較をスライドする役目。
→青矢印を、1からどこまでスライドするか
外側「i」ループは、巡を必要なだけする役目。
→データに応じて何巡させるか

「i」を、青矢印が”右端から何番手前まで進めるか”の上限決めに使ってます。

まずは正しく動くモノを作る

とはいえ、正しく動けば良いのです。

前節で、いきなり「length」で組みましたが（※ゆくゆくはそんぐらい出来るようになるとはいえ）。

最初はデータ数固定でも構いません。まずは比べる2つの配列要素（jとj+1）で上手いこと動くように組んで。

○手続き名: bubbleSort(整数型の配列: array)
  整数型: i, j, swap, length
  
  length ← arrayの要素数
  
  for (i を 1 から 3 まで 1 ずつ増やす)
    for (j を 1 から 4-i まで 1 ずつ増やす)
      if (array[j] > array[j + 1])
        swap ← array[j]
        array[j] ← array[j + 1]
        array[j + 1] ← swap
      endif
    endfor
  endfor

i=1の時、
　j=1。array[1]とarray[2]
　j=4-i=4-1=3。array[3]とarray[4]
i=3の時、
　j=1。array[1]とarray[2]
　j=4-i=4-3=1。array[1]とarray[4]
図解通りに比べてくれそうですし、配列arrayの[1]～[4]に収まってますね（範囲外の[0], [-1], [5]が出なくて良かった）。

後から”データ数が変わっても動くように, 要素数（lenght）”を導入すれば良いのです。

効率化のループ離脱タイミング

データによっては、全ループが実行される前に、完全に並べ終わってることもありますね。

例えば、データが元々昇順に並んでた場合。

1巡目（①～③）で、全データを見終わって、並べ替えが発生しなかったなら、「調べる前から並んでた。これ以上処理することはない」って、ループを途中で止めます（break）。

「なんで①で止めないのかな？」と思った方、鋭いです。そして残念ながら間違い（私も間違えました💦）。

他データ（4例）でチェック。左から1, 2, 3例は1巡目終了時に並べ切ってます。一見すると、処理を止めて良さそうですが。4例目のように不完全な場合があります。

ある巡目で入替が発生したら処理を止めてはダメです。ある巡目で入替が発生しなかったら止めてOK。

ループ離脱のタイミング/範囲

ある巡目で「1回でも入替が起きたら、処理を止めちゃダメ。1回も入替が起きなかったら、処理を止めちゃう」を擬似言語に組込みます。

「ループ前に入替発生してないFalse」をキメウチして、入替発生時に「True」に書き換える処理。＞【擬似言語⑧】素数のNote(一度でも割り切れたら素数じゃないのでループ離脱)

○手続き名: bubbleSortOptimized(整数型の配列: array)
  整数型: i, j, swap, length
  論理型: isSwapped  // 交換があったかどうかを記録する変数
  
  length ← arrayの要素数
  
  for (i を 1 から length-1 まで 1 ずつ増やす)
    isSwapped ← false  // 新しい周回が始まるたびにリセット
    for (j を 1 から length-i まで 1 ずつ増やす)
      if (array[j] > array[j + 1])
        swap ← array[j]
        array[j] ← array[j + 1]
        array[j + 1] ← swap
        isSwapped ← true  // 1回でも交換が起きたらtrueにする
      endif
    endfor
   / 【ここがポイント】1周して一度も交換が起きていなければ、すでに整列完了 */
    if (isSwapped = false)
      forのループを抜ける  // ここで④以降のループをキャンセルして終了する
    endif
  endfor

入替フラグ(isSwapped)の書替えは、入替処理のとこは大丈夫ですが。ループ離脱のタイミング（break）、毎巡回リセット（false）する点に注意してください。

ループ離脱は、外側（i）ループで、全体的に抜けます。内側（j）ループで抜けてもソート処理は続きます（次巡）。

「isSwapped ← false」の初期化は、毎巡必要です。前巡で入替が発生して「true」になったのを、次巡には「false」にして入替が発生するか調べたいので。

その巡の最後まで入替が発生しなかったら(false)、離脱。

下図は1巡目で離脱するケース。

次は2巡目に離脱するケース。

1巡目で入替発生したので離脱せず(trueに変化)。2巡目へ。

でも2巡目始めに「false」に戻して、2巡目に入替発生するか見ます。2巡目最後まで入替発生しない（falseのまま）ので、離脱。

まとめ

お疲れ様でした！

ループ終了値が変化していく点、効率化のbreak。初学者さんには難しかったですね。でも図解にして少しは分かったなら嬉しいです。

でも今回のNoteは「これでも最短ストレート」に書きました。ループカウンタ「i」の使い方を違えたり、確定を「後ろから」にするアルゴリズムもあったり、別解がたっっっくさんあるんです。＞【擬似言語⑫裏】バブルソートの別解Note

さらに、バブルソートはソートの中でも最弱。私の専門学校でも1年生前期（夏休み前）には、バブルソート/選択ソート/挿入ソートの3種は必須です。＞他ソートのNote（企画中＊）

これにて、「Lv.2」シリーズは一応終了です。次回は「Lv.2裏」や「Lv.3」でお会いできたらと思います（※企画中なので、待たずに学習/受験をしていって下さいね💦）。

最後に私のお薦めの演習順番。
❶学習前の”分からせ”
＞【FEB】サンプル問題2のNote
❷テキスト
＞【FEB】擬似言語の教科書Note
＞【FEB】擬似言語の理解演習Note ←いまこの辺
↓※必要なら
うかる！ 基本情報技術者　[科目B・セキュリティ編](amazon)
うかる！ 基本情報技術者　[科目B・アルゴリズム編](amazon)
❸各年度の公開問題
＞【FEB】令和07年科目BのNote
＞【FEB】令和06年科目BのNote
＞【FEB】令和05年科目BのNote
➍解法の総復習（➋や➌と併用可）
＞【FEB】擬似言語の11の解法Note
➎模擬試験
＞【FEB】サンプル問題1のNote（擬似言語）
＞【FEB】サンプル問題1のNote（セキュリティ）