【擬似言語⑫裏】バブルソート | 向きと配列指定の別解（基本情報技術者, 科目B, アルゴリズム）

このNoteは、＞【擬似言語⑫】バブルソートのNote の裏面として「別の組み方」をしてみます。

ループカウンタの役割を変えて、色んなバブルソートをしてみます。擬似言語のトレースのスキルアップにつながるので考えながら読んで下さいね。

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

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

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

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

前回のおさらい

「バブルソート（隣接交換法）」は隣同士を比べて入れ替えて並べ替え（ソート）する手法でした（wikipedia）。

＞前回のNote では「前から」2つずつ比べて、「後ろに」大きい値を追いやり「確定」する方針でした。

擬似言語では、外ループ（i）で比べる範囲を狭める役割、内ループ（j）で比較する2値をズラしていく役割をしました。

○手続き名: 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

＞前回のNoteでは更に、効率化（breakでループ離脱）もしましたが、今後の本筋のノイズになるのでここまでとします。

ループカウンタの別解釈

前節では、「i」を青矢印が”右端から何番手前まで進めるか”の上限決めに使ってます。jの終値を「length - i」で変化させてます。

  for (i を 1 から length-1 まで 1 ずつ増やす)
    for (j を 1 から length-i まで 1 ずつ増やす)

ここでは、「i」を”左端から何番目まで進めるか”の上限決めに使ってみます。iとjの終値を変えますよ。

図解で比較します。

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

ループカウンタの「減らす」と「増やす」が混合してて、私は気持ち悪いですが。

私は「2まで」が中途半端と思ったので、「1まで」に調整。

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

擬似言語の該当部分だけ比べて見ます。

/ 前回のNote */  
for (i を 1 から length-1 まで 1 ずつ増やす)
    for (j を 1 から length-i まで 1 ずつ増やす)

/ 今回 */
  for (i を length-1 から 1 まで 1 ずつ減らす)
    for (j を 1 から i まで 1 ずつ増やす)

今回の方は、「jを1からiまで」で進み方が分かり易いかな。一方で、「iを～減らす」が「jを～増やす」と混ざるのが、個人的に気持ち悪いですが。でも見てたら分かり易く感じてきました。

iやjの始値/終値が全然違うのに、jは同じになります。青矢印がarray[j]。

逆向きアルゴリズム

＞前回のNote は「前から」比較して「後ろから」確定させていきました。私には分かり易いです。

「逆向き」のアルゴリズムを組めます。「後ろ」から比較して「前から」確定。