選択ソートの比較回数と交換回数を求める

解説

選択ソートは、未整列部分から最小値を見つけて先頭と交換する処理を繰り返す。配列 data = {5, 3, 8, 1, 4}（要素数 n = 5）について各パスをトレースする。 【i = 1】minIdx = 1（値 5） j=2: 3 < 5 → minIdx=2、j=3: 8 < 3? No、j=4: 1 < 3 → minIdx=4、j=5: 4 < 1? No 比較 4 回（compCount=4）。minIdx=4 ≠ 1 → 交換（swapCount=1）。data = {1, 3, 8, 5, 4} 【i = 2】minIdx = 2（値 3） j=3: 8 < 3? No、j=4: 5 < 3? No、j=5: 4 < 3? No 比較 3 回（compCount=7）。minIdx=2 = 2 → 交換なし（swapCount=1）。data = {1, 3, 8, 5, 4} 【i = 3】minIdx = 3（値 8） j=4: 5 < 8 → minIdx=4、j=5: 4 < 5 → minIdx=5 比較 2 回（compCount=9）。minIdx=5 ≠ 3 → 交換（swapCount=2）。data = {1, 3, 4, 5, 8} 【i = 4】minIdx = 4（値 5） j=5: 8 < 5? No 比較 1 回（compCount=10）。minIdx=4 = 4 → 交換なし（swapCount=2）。data = {1, 3, 4, 5, 8} 最終結果: compCount = 10、swapCount = 2。よって正解はイである。

選択肢ごとの解説

ア

compCount を data[j] < data[minIdx] が成立した回数(真になった回数)だけ数えた場合にこの値になる。しかし compCount の加算は if 文の外にあり、比較の成否にかかわらず毎回加算されるため誤りである。

イ

正解。内側ループの比較回数は 4+3+2+1 = 10 回。交換は i=1 と i=3 の 2 回だけ発生する。

ウ

交換によって配列が更新されることを反映せず、常に初期状態 {5,3,8,1,4} のままトレースすると i=1, i=2, i=3 で minIdx ≠ i となり swapCount を 3 と誤る。

エ

外側ループの繰返し回数 n-1 = 4 をそのまま swapCount と誤解した場合にこの値になる。実際には minIdx = i のとき交換は行われない。

オ

内側ループの比較 10 回に加え、外側ループ末尾の minIdx ≠ i の判定 4 回も compCount に含めてしまうと 14 になる。しかしこの判定では compCount は加算されない。

カ

オの比較回数の誤り(14)とウの交換回数の誤り(3)を同時に犯した場合の組合せであり、二重に誤っている。

登録すると解いた結果が残り、間違えた問題は日をおいて復習に出ます。