多重ループを使うバブルソート｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
2023-03-06 更新
基本情報技術者試験は、 2023 年 4 月から新制度で実施されます。
この連載では、新制度で採用される新しい擬似言語（旧制度の擬似言語とは、表記方法に違いがあります）を使って、試験のシラバス（情報処理技術者試験における知識・技能の細目）に示されている代表的なアルゴリズムとデータ構造を、プログラミング入門者向けにやさしく解説します。 受験対策としてだけでなく、アルゴリズムとプログラミングの基礎知識を習得するために、ぜひお読みください。
今回は、多重ループを使うソートアルゴリズムである バブルソート を取り上げます。
もくじ
前提知識として多重ループの流れを知る
ソート（ sort = 整列） とは、配列の要素を昇順（小さい順）または降順（大きい順）に並べ替えることです。
試験のシラバスには、ソートアルゴリズムとして、
- バブルソート
- 選択ソート
- 挿入ソート
- クイックソート
- マージソート
- ヒープソート
が示されています。
これらの中で、バブルソート、選択ソート、挿入ソートは、繰り返しの中に繰り返しがある多重ループ（ loop = 繰り返し）を使うという点で共通しています。 今回は、バブルソートだけを取り上げますが、多重ループでソートを行うポイントをつかめれば、選択ソートと挿入ソートも容易に理解できるでしょう。 クイックソート、マージソート、ヒープソートに関しては、別の機会に取り上げます。
バブルソートのアルゴリズムを理解するための前提知識として、多重ループの流れを知っておきましょう。
多重ループという言葉だけを聞くと、とても難しく感じるかもしれませんが、日常生活にも普通に存在するものであり、決して難しくありません。 たとえば、 0 時 0 分から 23 時 59 分まで変化する 1 日の時計（デジタル時計）は、多重ループの好例です。 時の繰り返しの中に、分の繰り返しがあるからです。
多重ループを使って 1 日の時計を表示するプログラム
リスト 1 は、 1 日の時計を擬似言語のプログラムにしたものです（わかりやすいように色分けしています）。
for 文は、繰り返しを表す構文であり、 for と endfor で囲まれた範囲にある処理が、 for の後のカッコの中にある制御記述（どのように繰り返すかを示した文や式など）に従って繰り返されます。
for 文のループ中に別の for 文のループがあることに注目してください。
外側のループでは、時を表す変数 hour が 0 から 23 まで 1 ずつ増えます。
内側のループでは、分を表す変数 minute が 0 から 59 まで 1 ずつ増えます。
この多重ループの中で「 hour 時 minute 分を表示する」という処理が切り返されます。
整数型: hour, minute for (hour を 0 から 23 まで 1 ずつ増やす) // 外側のループ for (minute を 0 から 59 まで 1 ずつ増やす) // 内側のループ hour 時 minute 分を表示する endfor endfor
多重ループの流れは「外側のループ変数（繰り返すたびに変化する変数）の値が固定された状態で、内側のループ変数が変化する」です。
リスト 1 の変化を順番に見てみましょう。
- 外側のループ変数 hour が 0 に固定された状態で、内側のループ変数 minute が 0 から 59 まで 1 ずつ変化
subdirectory_arrow_right これによって 0 時 0 分から 0 時 59 分までが表示 - 内側のループが終了すると、外側のループ変数 hour が変化
subdirectory_arrow_right ここでは、 1 ずつ増えるので、ループ変数 hour が 1 になる - ループ変数 hour が 1 に固定された状態で、内側のループに入り直す
- 再びループ変数 minute が 0 から 59 まで 1 ずつ変化
subdirectory_arrow_right これによって 1 時 0 分から 1 時 59 分までが表示
以下同様に、 2 時 0 分から 2 時 59 分まで、 3 時 0 分から 3 時 59 分まで、 ……. 23 時 0 分から 23 時 59 分までが表示され、外側のループの終了によって、多重ループ全体が終了します。
リスト 1 では、 for 文の中に別の for 文がある多重ループの例を示しましたが、 whil e文や do ～ while 文を使って多重ループを作ることもできます。 どの場合でも、多重ループは、外側のループ変数の値が固定された状態で、内側のループ変数が変化する、という流れになります。
バブルソートのアルゴリズムを理解する
バブルソートのアルゴリズムを大雑把に説明すると
「配列の後ろから前に向かって、
- 隣り合った要素（ある要素と 1 つ前の要素）を比較
- 小さい方が前になるように交換
という処理を繰り返す」です。
池の底から表面に泡が浮き上がるように、配列の後ろから前に小さな値が浮かび上がるので、バブル（ bubble = 泡）ソートと呼ぶのです。
プログラムを示す前に、手作業でバブルソートをやってみましょう。
図 1 に手順を示します。ここでは、要素数 4 個の配列 a を昇順にソートしています。 配列の要素番号（添字やインデックスとも呼びます）は、 1 から始まるとします。
図 1 の手順を理解できたら、どのようなループ変数の多重ループで、どのような処理が繰り返されるかを考えてみましょう。
バブルソートでは、決定する位置と比較位置が変化していきます。 後で示すプログラムに合わせて、決定する位置を変数 num 、比較位置を変数 pos で表すことにします。
- num を 1 に固定した状態で、 pos が 4 から 2 まで変化
- num を 2 に固定した状態で、 pos が 4 から 3 まで変化
- num を 3 に固定した状態で、 pos が 4 から 4 に変化
（ 4 と 4 は同じ値ですが他に合わせて変化と考えてください）
このことから、 num が外側のループ変数であり、 pos が内側のループ変数であることがわかります。
外側のループ変数 num は、 1 （配列の先頭）から 3 （配列の末尾より 1 つ前の要素）まで 1 ずつ増えて変化します。 1 から 4 （配列の末尾の要素）でないのは、配列の末尾より 1 つ前の要素が決定すれば、残りの 1 つとなった末尾の要素は自動的に決定するからです。
内側のループ変数 pos は、 4 （配列の末尾）から、現在決定しようとしている位置 num の 1 つ右 (num + 1 ) まで 1 ずつ減って変化します。
多重ループで繰り返される処理は「比較位置の要素と 1 つ前の要素を比較し、小さい方が前になるように交換する」です。
配列の名前を a とすれば、
比較位置の要素は a[pos] であり、
1 つ前の要素は a[pos - 1] です。
a[pos - 1] > a[pos] という条件が真なら、 a[pos] と a[pos - 1] の値を交換します。
バブルソートのプログラムを読み取る
バブルソートが、どのようなループ変数の多重ループになり、どのような処理が繰り返されるかを理解できたらなら、プログラムも容易に理解できるでしょう。
リスト 2 は、先ほど図 1 で手順を示したバブルソートを擬似言語のプログラムにしたものです。
整数型の配列: a ← { 78, 56, 34, 12 }
は、「 78 」「 56 」「 34 」「 12 」という要素を持った配列 a を宣言しています。 整数型の変数 num と pos の役割は、これまでの説明と同じです。 整数型の変数 temp （ temporary = 一時的、という意味です）は、要素の値を交換するときに使います。
整数型の配列: a ← { 78, 56, 34, 12 }
整数型: num, pos, temp
for (num を 1 から 3 まで 1 ずつ増やす) // 外側のループ
for (pos を 4 から num +1 まで 1 ずつ減らす) // 内側のループ
if (a[pos - 1] > a[pos])
temp ← a[pos]
a[pos] ← a[pos - 1]
a[pos - 1] ← temp
endif
endfor
endfor
変数 temp を使った値の交換も、覚えておくべきアルゴリズムです。 ここでは、 a[pos] と a[pos - 1] の値を交換します。
もしも、いきなり a[pos] ← a[pos - 1] を行ったら a[pos] の値が失われてしまうので、その前に
temp ← a[pos]
で a[pos] の値を変数 temp に一時的に逃がします。 temp ← a[pos] の後で、 a[pos] ← a[pos - 1] を行い、最後に
a[pos - 1] ← temp
を行えば、 a[pos] と a[pos - 1] の値を交換できます。
バブルソートの穴埋め問題にチャレンジする
試験対策として、バブルソートの穴埋め問題にチャレンジしてみましょう。
整数型の配列: a ← { 90, 78, 56, 34, 12 } 整数型: num, pos, temp for (a) // 外側のループ for (b) // 内側のループ if ([pos - 1] a[pos]) temp ← a[pos] a[pos] ← a[pos - 1] a[pos - 1] ← temp endif endfor endfor
解答群
| a | b | |
|---|---|---|
| ア | pos を num + 1 から 5 まで 1 ずつ増やす | num を 4 から 1 まで 1 ずつ減らす |
| イ | num を 4 から 1 まで 1 ずつ減らす | pos を num + 1 から 5 まで 1 ずつ増やす |
| ウ | pos を 5 から num + 1 まで 1 ずつ減らす | num を 1 から 4 まで 1 ずつ増やす |
| エ | num を 1 から 4 まで 1 ずつ増やす | pos を 5 から num + 1 まで 1 ずつ減らす |
要素数が増えても、アルゴリズムは同じです。
外側のループ変数 num は、配列の先頭から末尾より 1 つ前まで 1 ずつ増えて変化します。
内側のループ変数 pos は、配列の末尾から現在決定しようとしている位置 num の 1 つ右 (num + 1) まで 1 ずつ減って変化します。
ここでは、配列の要素が a[1] から a[5] なので、外側の for 文の制御記述は
num を 1 から 4 まで 1 ずつ増やす
であり、内側の for 文の制御記述は
pos を 5 から num + 1 まで 1 ずつ減らす
です。
したがって、選択肢エが正解です。
今回は、多重ループを使うソートアルゴリズムであるバブルソートを取り上げました。
次回以降も、シラバスに示されたアルゴリズムとデータ構造を学んでいきます。
それでは、またお会いしましょう！
label 関連タグ免除試験を受けた 74.9% の方が、科目A免除資格を得ています。
マージソート｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
二分木の深さ優先探索と幅優先探索｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
比べてわかるキューとスタックの仕組み｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
「リスト」というデータ構造｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
サーチのアルゴリズム (3) ハッシュ表探索法のアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
クイックソートのアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
再帰呼び出しのアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
サーチのアルゴリズム (2) 二分探索法｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
サーチのアルゴリズム (1) 線形探索法｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update
多重ループを使うバブルソート｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門
update『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”
大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。
主な著作物
- 「プログラムはなぜ動くのか」（日経BP）
- 「コンピュータはなぜ動くのか」（日経BP）
- 「出るとこだけ! 基本情報技術者」 (翔泳社)
- 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
- 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ） など多数
