科目B頻出のソート・探索を擬似言語で読み解く力を身につけましょう。
日野 こむぎ
ソートを擬似言語で読むの、難しそう…
藤森 さやか 先生
大丈夫、定型のパターンだから慣れれば読めるようになるわ。
まずはバブルソートの例から見てみましょう。
○ 手続: bubbleSort(整数型の配列: a)
整数型: i, j, temp
for (i を 1 から aの要素数 - 1 まで 1 ずつ増やす)
for (j を 1 から aの要素数 - i まで 1 ずつ増やす)
if (a[j] > a[j + 1])
temp ← a[j]
a[j] ← a[j + 1]
a[j + 1] ← temp
endif
endfor
endfor
青木 澪
外側のループは「何回スキャンするか」、内側のループは「隣接要素を比較・交換」する処理ね。
桃井 すみれ
二分探索もよく出る問題ですよねぇ
○ 手続: binarySearch(整数型の配列: a, 整数型: key)
整数型: low, high, mid
low ← 1
high ← aの要素数
while (low ≦ high)
mid ← (low + high) ÷ 2
if (a[mid] = key)
return mid
elseif (a[mid] < key)
low ← mid + 1
else
high ← mid - 1
endif
endwhile
return -1
青木 澪
中央 (mid) を見て、key と比較するの。
等しければ位置を返して、key が大きければ後半 (low を更新)、小さければ前半 (high を更新)。
見つからなければ -1 を返すのよ。
日野 こむぎ
二分探索は O(log n) で速いんだよね!
あたし、こういうの大好き!
藤森 さやか 先生
そう。
試験では「mid の値が何回更新されるか」「ループ何回で見つかるか」のような問題がよく出るわ。
具体的な配列でトレースして数えるのが正攻法ね。
確認クイズ
上記の binarySearch に配列 {1, 3, 5, 7, 9, 11, 13} と key = 11 を渡した場合、何回ループを実行するか。
- 1回
- 2回
- 3回
- 4回
こたえを見る
正解: 3. 3回
1回目: low=1, high=7, mid=4, a[4]=7<11, low=5。2回目: low=5, high=7, mid=6, a[6]=11=11, mid=6を返す。実は2回目で見つかります。「3回」を選んだ場合は終了の前のループも数えていますが、実行されるのは2回。... 修正: 1回目: mid=4, 7<11→low=5。2回目: mid=(5+7)/2=6, a[6]=11→ヒット。よって 2回です。
