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

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

ア.左側に [2, 4, 1, 5, 3]、ピボット 7、右側に [9] が並ぶ正解

イ.左側に [2, 4, 1]、ピボット 7、右側に [9, 5, 3] が並ぶ

ウ.左側に [1, 2, 3, 4, 5]、ピボット 7、右側に [9] が並ぶ

エ.左側に [2, 9, 4]、ピボット 7、右側に [1, 5, 3] が並ぶ

解説

クイックソートは「将軍が軍を2つに分ける」ようなアルゴリズム。ピボットより小さい者は左、大きい者は右に分かれる。

なぜアが正解か

ピボット=7。配列の残り要素を比較: 2<7, 9>7, 4<7, 1<7, 5<7, 3<7。7より小さい要素: [2,4,1,5,3]、7より大きい要素: [9]。分割後は [2,4,1,5,3 | 7 | 9] の形になる。左側の順序は未ソートのまま。

なぜイは間違いか

左側に [2,4,1] と右側に [9,5,3] は誤り。5と3は7より小さいので左側に入る。

なぜウは間違いか

左側が [1,2,3,4,5] と昇順に並んでいるのは誤り。1回の分割では左右の内部はソートされない。

なぜエは間違いか

左側に [2,9,4] は誤り。9>7なので9は右側に入らなければならない。

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

← 前の問題

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

次の問題 →

n個の要素をマージソートで整列するとき、マージ操作の回数として正しいものはどれか。8要素の場合は何回か。