多重ループを使うバブルソート｜新しい擬似言語で学ぶ 科目 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 分を表示する」という処理が切り返されます。

swipeプログラムは横スクロールできます

整数型: hour, minute
for (hour を 0 から 23 まで 1 ずつ増やす)		// 外側のループ
  for (minute を 0 から 59 まで 1 ずつ増やす)	// 内側のループ
    hour 時 minute 分を表示する
  endfor
endfor

多重ループの流れは「外側のループ変数（繰り返すたびに変化する変数）の値が固定された状態で、内側のループ変数が変化する」です。

リスト 1 の変化を順番に見てみましょう。

1. 外側のループ変数 hour が 0 に固定された状態で、内側のループ変数 minute が 0 から 59 まで 1 ずつ変化
   subdirectory_arrow_right これによって 0 時 0 分から 0 時 59 分までが表示
2. 内側のループが終了すると、外側のループ変数 hour が変化
   subdirectory_arrow_right ここでは、 1 ずつ増えるので、ループ変数 hour が 1 になる
3. ループ変数 hour が 1 に固定された状態で、内側のループに入り直す
4. 再びループ変数 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. 隣り合った要素（ある要素と 1 つ前の要素）を比較
2. 小さい方が前になるように交換

という処理を繰り返す」です。

池の底から表面に泡が浮き上がるように、配列の後ろから前に小さな値が浮かび上がるので、バブル（ bubble = 泡）ソートと呼ぶのです。

プログラムを示す前に、手作業でバブルソートをやってみましょう。

図 1 に手順を示します。ここでは、要素数 4 個の配列 a を昇順にソートしています。 配列の要素番号（添字やインデックスとも呼びます）は、 1 から始まるとします。

図 1 の手順を理解できたら、どのようなループ変数の多重ループで、どのような処理が繰り返されるかを考えてみましょう。

バブルソートでは、決定する位置と比較位置が変化していきます。 後で示すプログラムに合わせて、決定する位置を変数 num 、比較位置を変数 pos で表すことにします。

1. num を 1 に固定した状態で、 pos が 4 から 2 まで変化
2. num を 2 に固定した状態で、 pos が 4 から 3 まで変化
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

要素数が増えても、アルゴリズムは同じです。

外側のループ変数 num は、配列の先頭から末尾より 1 つ前まで 1 ずつ増えて変化します。
内側のループ変数 pos は、配列の末尾から現在決定しようとしている位置 num の 1 つ右 (num + 1) まで 1 ずつ減って変化します。

ここでは、配列の要素が a[1] から a[5] なので、外側の for 文の制御記述は

num を 1 から 4 まで 1 ずつ増やす

であり、内側の for 文の制御記述は

pos を 5 から num + 1 まで 1 ずつ減らす

です。

したがって、選択肢エが正解です。

今回は、多重ループを使うソートアルゴリズムであるバブルソートを取り上げました。

次回以降も、シラバスに示されたアルゴリズムとデータ構造を学んでいきます。

それでは、またお会いしましょう！

マージソート｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update 2023-12-13

二分木の深さ優先探索と幅優先探索｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update 2023-11-16

比べてわかるキューとスタックの仕組み｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update 2023-11-14

「リスト」というデータ構造｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update 2023-11-14

サーチのアルゴリズム (3) ハッシュ表探索法のアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update 2023-08-03

クイックソートのアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update 2023-07-19

再帰呼び出しのアルゴリズム｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update 2023-06-06

サーチのアルゴリズム (2) 二分探索法｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update 2023-05-09

サーチのアルゴリズム (1) 線形探索法｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update 2023-04-04

多重ループを使うバブルソート｜新しい擬似言語で学ぶ 科目 B アルゴリズムとプログラミング入門

update 2023-03-06

矢沢 久雄

『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”

大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。

主な著作物

• 「プログラムはなぜ動くのか」（日経BP）
• 「コンピュータはなぜ動くのか」（日経BP）
• 「出るとこだけ! 基本情報技術者」 (翔泳社)
• 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
• 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ）　など多数