擬似言語トレースドリル

隣どうしの比較と交換（1巡）｜擬似言語のトレース解説と練習問題

レベル：基礎　／　タグ：for・if・配列・交換・整列

関数 onePass は、配列 data の隣り合う要素を先頭から順に比べ、左が大きければ入れ替える。配列の要素番号は 1 から始まる。

プログラム

1○整数型の配列: onePass(整数型の配列: data)
2 整数型: j, tmp
3 for (j を 1 から dataの要素数 － 1 まで 1 ずつ増やす)
4 if (data[j] > data[j ＋ 1])
5 tmp ← data[j]
6 data[j] ← data[j ＋ 1]
7 data[j ＋ 1] ← tmp
8 endif
9 endfor
10 return data

何をしているか

隣り合う2つの要素を先頭から順に比べ、左のほうが大きければ入れ替えます。1巡すると、いちばん大きい要素が末尾まで運ばれます。これを繰り返すのがバブルソートです。

トレースのコツ

  • 比べるのは今の配列の j 番目と j ＋ 1 番目です。前の回で入れ替えていたら、入れ替えた後の値で比べます。
  • 配列をそのつど書き直すのが確実です。頭の中で動かすと、2回目あたりで元の並びと混ざります。
  • 交換が起きた回数と、比較の回数は別です。比較は「要素数 − 1」回です。

よくある間違い

  • 元の配列の値で比べ続ける。大きい要素は右へ運ばれていくので、同じ要素が何度も比較に出てきます。
  • 1巡で全部が整列すると考える。1巡で決まるのは末尾の1つだけです。
  • 繰返しの終わりを要素数にしてしまい、存在しない「j ＋ 1 番目」を見にいく。

例題：onePass({3, 7, 2, 5, 4, 9}) を最後まで追う

上のプログラムを onePass({3, 7, 2, 5, 4, 9}) で呼び出したときの、全ステップのトレース表です。太字は、その文で値が変わった変数です。

#行したことdatajtmp
12宣言{3, 7, 2, 5, 4, 9}未設定未設定
23繰返しの初期化{3, 7, 2, 5, 4, 9}1未設定
33条件判定（真）{3, 7, 2, 5, 4, 9}1未設定
44条件判定（偽）{3, 7, 2, 5, 4, 9}1未設定
53繰返しの更新{3, 7, 2, 5, 4, 9}2未設定
63条件判定（真）{3, 7, 2, 5, 4, 9}2未設定
74条件判定（真）{3, 7, 2, 5, 4, 9}2未設定
85代入{3, 7, 2, 5, 4, 9}27
96代入{3, 2, 2, 5, 4, 9}27
107代入{3, 2, 7, 5, 4, 9}27
113繰返しの更新{3, 2, 7, 5, 4, 9}37
123条件判定（真）{3, 2, 7, 5, 4, 9}37
134条件判定（真）{3, 2, 7, 5, 4, 9}37
145代入{3, 2, 7, 5, 4, 9}37
156代入{3, 2, 5, 5, 4, 9}37
167代入{3, 2, 5, 7, 4, 9}37
173繰返しの更新{3, 2, 5, 7, 4, 9}47
183条件判定（真）{3, 2, 5, 7, 4, 9}47
194条件判定（真）{3, 2, 5, 7, 4, 9}47
205代入{3, 2, 5, 7, 4, 9}47
216代入{3, 2, 5, 4, 4, 9}47
227代入{3, 2, 5, 4, 7, 9}47
233繰返しの更新{3, 2, 5, 4, 7, 9}57
243条件判定（真）{3, 2, 5, 4, 7, 9}57
254条件判定（偽）{3, 2, 5, 4, 7, 9}57
263繰返しの更新{3, 2, 5, 4, 7, 9}67
273条件判定（偽）{3, 2, 5, 4, 7, 9}67
2810戻る（{3, 2, 5, 4, 7, 9}）{3, 2, 5, 4, 7, 9}67

この例題で問われること

問　onePass({3, 7, 2, 5, 4, 9}) を呼び出したときの戻り値はどれか。

答え　{3, 2, 5, 4, 7, 9}

  • 戻り値になる data は、{3, 7, 2, 5, 4, 9} → {3, 2, 2, 5, 4, 9} → {3, 2, 7, 5, 4, 9} → {3, 2, 5, 5, 4, 9} → {3, 2, 5, 7, 4, 9} → {3, 2, 5, 4, 4, 9} → {3, 2, 5, 4, 7, 9} と変わります。
  • 10行目で返す時点の値 {3, 2, 5, 4, 7, 9} が答えです。

問　7行目を3回目に実行した直後の、変数 data の値はどれか。

答え　{3, 2, 5, 4, 7, 9}

  • 7行目は全部で3回実行されます。
  • 実行した直後の data は、順に {3, 2, 7, 5, 4, 9} → {3, 2, 5, 7, 4, 9} → {3, 2, 5, 4, 7, 9} です。
  • 3回目の直後なので、答えは {3, 2, 5, 4, 7, 9} です。

問　7行目が実行される回数はどれか。

答え　3

  • 7行目は3回実行されます。トレース表で 7行目の行を数えると確かめられます。

練習問題 標準（5問）

本試験と同じくらいの量。レベル：基礎

  1. 問題01　onePass({7, 2, 3, 9})
  2. 問題02　onePass({1, 2, 6, 4})
  3. 問題03　onePass({7, 3, 1, 8})
  4. 問題04　onePass({1, 5, 7, 3})
  5. 問題05　onePass({5, 4, 3, 9})
もっと解く（追加の10問）
  1. 問題06　onePass({1, 6, 5, 9})
  2. 問題07　onePass({4, 3, 8, 9})
  3. 問題08　onePass({8, 1, 3, 9})
  4. 問題09　onePass({5, 2, 9, 4})
  5. 問題10　onePass({3, 1, 6, 2})
  6. 問題11　onePass({6, 4, 7, 5})
  7. 問題12　onePass({3, 6, 5, 8})
  8. 問題13　onePass({2, 4, 3, 7})
  9. 問題14　onePass({5, 6, 4, 8})
  10. 問題15　onePass({7, 5, 9, 2})

練習問題 じっくり（10問）

長めのトレースで力をつける。レベル：基礎

  1. 問題01　onePass({3, 4, 1, 7, 6})
  2. 問題02　onePass({3, 8, 7, 6, 9, 5})
  3. 問題03　onePass({7, 5, 4, 2, 9, 1})
  4. 問題04　onePass({2, 6, 5, 7, 8, 4})
  5. 問題05　onePass({8, 4, 6, 9, 5})
  6. 問題06　onePass({5, 1, 7, 6, 4})
  7. 問題07　onePass({3, 2, 7, 5})
  8. 問題08　onePass({5, 6, 8, 2, 7})
  9. 問題09　onePass({7, 2, 8, 1, 4, 5})
  10. 問題10　onePass({4, 6, 5, 8, 7})
もっと解く（追加の20問）
  1. 問題11　onePass({1, 2, 5, 4, 3})
  2. 問題12　onePass({7, 8, 4, 9, 2})
  3. 問題13　onePass({4, 1, 5, 2, 9, 3})
  4. 問題14　onePass({2, 6, 5, 4, 9})
  5. 問題15　onePass({5, 7, 9, 1, 8})
  6. 問題16　onePass({2, 7, 9, 1, 8, 4})
  7. 問題17　onePass({6, 1, 9, 7})
  8. 問題18　onePass({5, 1, 6, 4, 9})
  9. 問題19　onePass({4, 3, 1, 2, 9, 6})
  10. 問題20　onePass({7, 4, 6, 3, 1, 8})
  11. 問題21　onePass({5, 3, 1, 9})
  12. 問題22　onePass({5, 2, 3, 7, 6})
  13. 問題23　onePass({5, 4, 6, 3})
  14. 問題24　onePass({1, 3, 5, 7, 6, 2})
  15. 問題25　onePass({6, 7, 2, 8, 3, 1})
  16. 問題26　onePass({2, 3, 4, 9, 8, 6})
  17. 問題27　onePass({5, 2, 8, 9, 6, 7})
  18. 問題28　onePass({4, 2, 1, 6, 7})
  19. 問題29　onePass({6, 4, 2, 9})
  20. 問題30　onePass({5, 6, 4, 1, 9, 2})

ほかのアルゴリズム