見出し画像

「情報関係基礎」過去問を教材化する：2008 バブルソート

クリヤキン

　大学入試センター試験2008年の情報関係基礎第3問はバブルソートである。プログラミングの初歩でよく題材とされる。for 文での繰り返しだけでできるので，学びはじめにはよい教材だろう。

=====================================

　春子，夏男，秋代，冬樹の４人がゲームを行った。この４人のゲームの得点は，この順に 73, 77, 81, 68 であった。この４人をゲームの得点が高い順に並べる。

その手順を次の図で説明しよう。名前と得点が組になって，全体がリストになっているものとする。図の ０，１，２，３ はリストの添え字である。

画像1

(a)〜(d) が第１段階で，左から順に隣り合う二人の得点を比べ，左の人の得点が低いときは入れ替える。
これを繰り返して２番と３番の比較まで終わると，一番得点の低い人（冬樹）が一番右にくる。
(e)〜(g)が第２段階で，第１段階と同様に進めていく。ただし，一番右は確定しているので，比べるのは１番と２番の要素までだ。
(h)(i) が第３段階。２番と３番は確定しているので，比較するのは０番と１番。
これでできあがる。

問１　上の並べ替えの手順をプログラムするのにあたって，リストの要素を入れ替える方法を考えよう。
data = [4, 1, 5, 2] というリストがあるとする。data[0]とdata[1] を入れ替えたい。このとき，
　data[0] = data[1]
としてしまうと，data は [1, 1, 5, 2] となって，４の値が失われてしまう。
そこで，data[0] の 4 をいったん他の変数に保存しておいて，data[0] = data[1]　とし，つぎに data[1] を保存した値にすればよい。

このやり方を次のようにプログラムした。空所を補充して完成しなさい。

data = [4, 1, 5, 2]
memo = 
data[0] = data[1]
data[1] =
print(data)

問２　先に示した並べ替えの手順を次のように整理した。（　）に適する数を入れなさい。

第１段階　０番から２番まで，その右隣と比較して，右が小さければ入れ替える。
第２段階　０番から（ア）番までその右隣と比較して右が小さければ入れ替える。第３段階　（イ）番をその右隣と比較して右が小さければ入れ替える。
以上で終わる。データが４つなので，（ウ）段階で終わる。

問３　並べ替えの手順を次のようにプログラムした。４，５，６，８行目の空所を補って完成しなさい。なお，それぞれの人の得点は，リスト score の第１要素なので，i 番目の人の得点は score[i][1] で表すことができる。
なお，２行目の  len(score) は score の要素の数を表す。今は 4 なので n は 3 になる。したがって，３行目で，j は 3, 2, 1 という値をとる。

score = [["春子", 73], ["夏男", 77], ["秋代", 81], ["冬樹", 68]]
n = len(score) - 1 
for j in range(n, 0, -1):
   for i in range( ):
       if score[i][1] <  :
           memo = 
           score[i] = score[i+1]
           score[i+1] = 
print(score)

 このやり方で並べ替えはできたが，よく考えると，手順を省略することができそうだ。
手順１で，(d) の春子と冬樹はそのままで入れ替えは行わず，この時点で，２番目（春子）と３番目（冬樹）の順序は確定している。したがって，次は０番目（秋代）と１番目（夏男）だけを比較すればよく，これで終わる。

画像2

　そこで，アルゴリズムを次のように修正した。

問４　次の文章の（　）に適する数を答えなさい。

・最後に入れ替えを行った番号を記憶する。それ以降は順序が確定している。
　この番号を saigo とする。はじめは saigo は３としておく。
　saigo の手前まで比較をしていけばよいが，saigo は書き換えられるので，
 　j  =  saigo として，j の手前まで比較していく。
・第１段階で，最後に入れ替えたのは（ア）番と（イ）番なので， saigo は １となる。
・次の段階では，（エ）番まで比較をすればよい。

問５　問４の考え方に従って，次のようにプログラムを書いた。４，５，６，８行目の空所を補って完成しなさい。

score = [["春子", 73], ["夏男", 77], ["秋代", 81], ["冬樹", 68]]
saigo = len(score) - 1
while saigo > 0:
   j = saigo
   saigo = 0
   for i in range( ):
       print(saigo,j,i)
       if score[i][1] < score[i+1][1]:
           memo = 
           score[i] = score[i+1]
           score[i+1] =
           saigo = 
   j = saigo
print(score)

================================

もとの問題を見てもらえばわかるが，こちらの方が少し難しく，同じにはならない。たとえば，下から２行目は，問いにはなっていないが，元の問題では j ← saigo - 1 であるが，ここでは j = saigo　である。それは，range(n) が，０から n までではなく，n-1 までであることに起因している。
　その他，インデックスが０スタートであることも，すこし難しい。
ものを数えるとき，ふつうは１から数えるだろう。Pythonでは，０からになる。CindyScript や Julia では１からだ。生徒にとっては「１から」の方が自然なので，Python や JavaScript の「０から」に慣れるまで時間がかかりそうだ。中には，何度説明してもわからない（数えられない）生徒もいるだろう。
　したがって，生徒の状況によっては，空欄の箇所を変えるほうがいいかもしれない。