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