【擬似言語⑫裏】バブルソート | 向きと配列指定の別解（基本情報技術者, 科目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 は「前から」比較して「後ろから」確定させていきました。私には分かり易いです。
「逆向き」のアルゴリズムを組めます。「後ろ」から比較して「前から」確定。
【課題】練習がてら、擬似言語を作ってみて下さい。
