-
![]()
-
![]()
次の生徒 (S) と先生 (T) の会話文を読み, 空欄 ア
解答群のうちから一つずつ選べ。
キ
に入れるのに最も適当なものを、後の
SAG
(A)
(6)
T:データを昇順または降順に並べ替えるアルゴリズムのことをソートといいます。まずはじめに、バブルソー
トというアルゴリズムを考えてみましょう。バブルソートは、配列の中の隣り合うデータの大小を比較し交
換を繰り返す方法です。 図1は、10個の要素を持つ配列 Data に対してバブルソートを行う場合の流れを
表しています。 グラムの4258
まず、配列の先頭とその次の要素を比較し,左の方が大きければ右と交換する。これを一つずつずらしなが
ら配列の最後尾まで繰り返していき、最後尾まで繰り返したら1周目の比較が終了します。
S: つまり, 1周目の比較がすべて終了した段階で、配列の最後尾にはア
| が入っているのですね。
T:その通りです。 2周目は、配列のイ を除いて1周目と同じように比較していきます。 これを繰り返
して,最後には配列が並び変わっているという具合ですね。図2はバブルソートのプログラムを表してい
ます。 その通りです
(SI)
し 配列 Data
77
52
89
48
97
3
18
62
33 29
1周目/ 1回目の比較
が配列の中
77
52
89
48
97
3
18
62
33
29
交換する
1周目/ 2回目の比較
52
77
89
48
97
3
18
62
33
29
交換しない
4357
1周目/3回目の比較
52
77
89 48 97
交換する
3
18
62
33
29
図1 配列 Data に対するバブルソートの流れ
国の
(1)
(2)
(3)
(4)
(5)
(6)b
Data = [77,5289,48,973 18,62,33,291
kazu= 要素数 (Data)
JRS pin
iを1からkazu-1まで1ずつ増やしながら繰り返す:
inshid
jを0から ウ まで1ずつ増やしながら繰り返す:
もしData[j] > Data [j + 1] ならば:
hokan
エ
Data[j] ①
<[abia] ada
rabid k
== [abis) stad
0000
Data(+11
Anda >
(7)
(8)
(7)
Data[j + 1] = hokan
図2 バブルソートのプログラム
(hidaes mig)
S:図2のプログラムだと, もし仮に最初からデータが昇順に並んでいても, 配列 Data の場合と同じ回数だけ
比較を繰り返さないといけないですよね?
T:いいところに気が付きましたね。 最初から昇順に整列された配列をバブルソートすると、交換回数は
オ だけど比較回数は
ので効率が悪いです。 それでは, データの整列が完了した段階で繰り返
しを抜けるように図1のプログラムを修正してみましょう。 まず, 変数 koukan を用意して初期化してお
きます(図3の (3) 行目)。 次に, 交換が発生した場合, 変数 koukan に 「1」 を代入するようにしましょ
(図3の (10) 行目)。 さて、ここで図4のプログラムを,図3のプログラムのどこに挿入すればいいか
分かりますか?
S:繰り返しが1周終わるごとに変数 koukan の値を確認する必要がありますから、
T: 正解です! よくできました。
キ
だと思います。
98
第3章 コンピュータとプログラミング
もし
kouk
