アルゴリズムとプログラミングアルゴリズムとデータ構造

挿入ソートで配列 [5, 3, 8, 1, 6] を昇順に整列する。2回の挿入操作（3を挿入、次に8を確認）を行った後の配列の状態として正しいものはどれか。

ア.[3, 5, 1, 8, 6]

イ.[3, 5, 6, 1, 8]

ウ.[3, 5, 8, 1, 6]正解

エ.[1, 3, 5, 8, 6]

解説

挿入ソートは「手持ちのトランプを整理する」ようなアルゴリズム。1枚ずつ正しい位置に差し込んでいく。

なぜウが正解か

Step1: 3を挿入。3<5なので3と5を交換 → [3, 5, 8, 1, 6]。Step2: 8を確認。8>5なので交換不要、位置はそのまま → [3, 5, 8, 1, 6]。2回の操作後はウの状態になる。

なぜアは間違いか

[3, 5, 1, 8, 6] は3回目の操作（1の挿入）の途中経過（1回目の交換直後）であり、挿入が完了すると[1, 3, 5, 8, 6]（エ）になる。

なぜイは間違いか

[3, 5, 6, 1, 8] は6と8が入れ替わっており、この時点では6はまだ操作されていない。

なぜエは間違いか

[1, 3, 5, 8, 6] は複数回の操作が完了した状態で、2回の挿入操作後ではない。

出典: AI生成問題（学習用）

この分野の解説記事

科目Bの歩き方 — 擬似言語は「3つの型」で読む

← 前の問題

A*アルゴリズムについての説明として最も正しいものはどれか。

次の問題 →

クイックソートで配列 [7, 2, 9, 4, 1, 5, 3] を昇順に整列する。先頭要素7をピボットとして1回の分割操作を行った後の状態として正しいものはどれか。