コンピュータ演習II 第11回 ドリル（授業中に解いて提出）¶
この問題集は、授業中に、解説を聞きながら自分の手を動かして解く 練習です。第11回の教材で学んだ 整列アルゴリズム（バブルソートと選択ソート） を、各節 1〜2 問ずつ練習します。
各問は「好きな値で入力を作り、こう処理してください」という形です。入力のリストは自分で自由に作ってください。作り方は各問の「入力の作り方」に示します。
進め方は次のとおりです。
- 配布の 解答用テンプレート
2xBxxxxx_11_drill.ipynbを Colab で開き、各問題の「入力の作り方」に従って自分でリストを作り、その下に処理を書いて実行してください。 - 各問に 入力例と出力例 を載せています。イメージがつかめないときは、まず入力例のとおりに動かしてから、自分の値に変えてください。
- 各問題に ヒントのフローチャート を載せていますが、一部 空欄（？①や？②）のブロックがあります。空欄に入る内容を自分で考えてみてください。フローチャートを完成させて流れをつかんでから、それを Python に翻訳して書いてください。ヒント図の変数名は例です。自分でつけた名前に読み替えてください。
- できたら、テンプレートを .py 形式でダウンロードして提出 してください。答え合わせはしません。自分で入力を決めて、思ったとおりに動くかを確かめることが目的です。
- わからなくなったら、第11回の教材を見返してかまいません。答えを写すのではなく、書き方を思い出して自分で書く ことが大切です。
なお、この演習では Colab のコード生成（生成AI の補完）は使わないでください。自分でプログラムを書いて、読めるようになることが目的です。
1. 隣同士の交換の復習¶
問題 1: 1パス（第09回の復習）¶
好きな整数を5 個入れたリストを numbers という名前で作ってください。第09回で学んだ 1パス（左から右へ、隣同士を比べて左が大きければ入れ替える操作を1 回通す）を行い、終わったら numbers を出力してください。入れ替えは tmp を使った3 行の書き方（swap）で書きます。1パスが終わると、いちばん大きい値が右端に来る ことを確かめてください。
入力の作り方:
numbers = [好きな整数を5 個]
入力例:
numbers = [5, 3, 8, 2, 7]
出力例（入力例のとき）:
[3, 5, 2, 7, 8]
これは例です。自分で決めた値で作ってかまいません（その場合、出力は例とは変わります）。
考えるポイント: 「左の方が大きければ入れ替える」は、どんな条件式で書けるでしょうか。ヒント図は if の条件が空欄？①です。
フローチャートの？①に入る内容を考えて、図を完成させてから Python に翻訳してください。
ヒント（フローチャート）:
2. バブルソート¶
問題 2: バブルソートで昇順に整列¶
問題1 と同じリスト numbers を使ってください。問題1 の「1パス」を 外側のループで繰り返す と、リスト全体が小さい順（昇順）に並びます。これが バブルソート です。2重ループで numbers を昇順に整列し、ループがすべて終わったら最後に1 回だけ numbers を出力してください。パスを重ねるごとに右端から順に確定していくので、内側のループの回数は1パスごとに1 回ずつ減らせます。
入力の作り方:
問題1 と同じリスト numbers
入力例:
numbers = [5, 3, 8, 2, 7]
出力例（入力例のとき）:
[2, 3, 5, 7, 8]
これは例です。自分で決めた値で作ってかまいません（その場合、出力は例とは変わります）。
考えるポイント: i 回目のパス（i は 0 から数えます）では、内側のループを何回まで回せばよいでしょうか。右端の i 個はすでに確定しています。ヒント図は内側のループの範囲が空欄？①です。
フローチャートの？①に入る内容を考えて、図を完成させてから Python に翻訳してください。
ヒント（フローチャート）:
問題 3: 各パスの終わりにリストを出力¶
問題2 と同じバブルソートで、こんどは 各パスが終わるたびに numbers を出力してください（最後の1 回だけではなく、外側のループ1 回ごとに1 行出力します）。パスを重ねるごとに、大きい値が右へ動いて確定していく様子が見えます。
入力の作り方:
問題1 と同じリスト numbers
入力例:
numbers = [5, 3, 8, 2, 7]
出力例（入力例のとき）:
[3, 5, 2, 7, 8]
[3, 2, 5, 7, 8]
[2, 3, 5, 7, 8]
[2, 3, 5, 7, 8]
これは例です。自分で決めた値で作ってかまいません（その場合、出力は例とは変わります）。
考えるポイント: print(numbers) はどこに置けばよいでしょうか。内側のループの中でも、2重ループの外でもありません。ヒント図は if の条件が空欄？①です（出力の位置は図に描いてあります）。
フローチャートの？①に入る内容を考えて、図を完成させてから Python に翻訳してください。
ヒント（フローチャート）:
3. 操作の回数を数える¶
問題 4: 交換回数を数える¶
問題2 のバブルソートに、入れ替え（交換）が起きた回数 を数える変数 count を付け足してください。count = 0 から始めて、交換したときだけ1 増やします。ループがすべて終わったら、整列した numbers と count をそれぞれ出力してください。
入力の作り方:
問題1 と同じリスト numbers
count = 0
入力例:
numbers = [5, 3, 8, 2, 7]
count = 0
出力例（入力例のとき）:
[2, 3, 5, 7, 8]
5
これは例です。自分で決めた値で作ってかまいません（その場合、出力は例とは変わります）。
考えるポイント: count = count + 1 はどこに置けばよいでしょうか。「比べたとき」ではなく「交換したとき」だけ数えます。ヒント図は True 側の最後の処理が空欄？①です。
フローチャートの？①に入る内容を考えて、図を完成させてから Python に翻訳してください。
ヒント（フローチャート）:
4. 選択ソート¶
問題 5: 最小値の位置を探す¶
好きな整数を5 個入れたリストを numbers という名前で作ってください（問題1 と同じでもかまいません）。リスト全体から いちばん小さい値の位置（添字）を探して、最後にその位置 min_index を出力してください。min_index = 0 から始めて、numbers[min_index] より小さい値を見つけるたびに min_index を更新します。これは次の問題で使う、選択ソートの部品です。
入力の作り方:
numbers = [好きな整数を5 個]
入力例:
numbers = [5, 3, 8, 2, 7]
出力例（入力例のとき）:
3
これは例です。自分で決めた値で作ってかまいません（その場合、出力は例とは変わります）。
考えるポイント: 「今までの最小より小さい値を見つけた」は、どんな条件式で書けるでしょうか。また、そのとき何を更新すればよいでしょうか。ヒント図は if の条件？①と、True 側の処理？②が空欄です。
フローチャートの？①と？②に入る内容を考えて、図を完成させてから Python に翻訳してください。
ヒント（フローチャート）:
問題 6: 選択ソートで昇順に整列¶
問題5 と同じリスト numbers を使ってください。問題5 の「最小値の位置探し」を外側のループで繰り返すと 選択ソート になります。各パスでは、まだ確定していない範囲（i 番目から右）の中から最小値の位置 min_index を探し、見つけたら i 番目の要素と交換します。ループがすべて終わったら最後に1 回だけ numbers を出力してください。
入力の作り方:
問題5 と同じリスト numbers
入力例:
numbers = [5, 3, 8, 2, 7]
出力例（入力例のとき）:
[2, 3, 5, 7, 8]
これは例です。自分で決めた値で作ってかまいません（その場合、出力は例とは変わります）。
考えるポイント: 各パスの探し始めでは、min_index を何に戻せばよいでしょうか。問題5 では 0 から始めましたが、このパスで確定させたいのは i 番目です。ヒント図は外側のループ本体の先頭の処理が空欄？①です。
フローチャートの？①に入る内容を考えて、図を完成させてから Python に翻訳してください。
ヒント（フローチャート）:
まとめ¶
この回のドリルでは、第11回で学んだ2 つの整列アルゴリズムを、教材の例から一歩ずらした形で練習しました。次のパターンを、見なくても書けるようにしておきましょう。
- バブルソートの骨格: 「1パス」（第09回）を外側のループで繰り返す。内側の範囲を
len(numbers) - 1 - iにすると、確定した右端を比べ直さずにすむ。 - パスごとの観察:
print(numbers)を外側のループの中（内側のループの後）に置くと、1パスごとの途中経過が見える。置く場所で出力の回数が変わる。 - 回数のカウント: 交換回数は
count = count + 1を if の中（swap の後）に置いて数える。比較回数なら if の前に置く。 - 選択ソートの骨格: 各パスで
min_index = iから探し直し、内側のループで最小値の位置を更新してから、i番目と1 回だけ交換する。 - 2 つのソートの対比: バブルソートは「比べるたびに交換する」、選択ソートは「探してから1 回だけ交換する」。骨格は同じ2重ループでも、交換の回数が変わる。
授業後の 課題 では、これらを自分の学籍番号から作るリストで解きます。ここで手を慣らしておきましょう。