クイックソートの手順をほかの整列法と見分ける
基本情報技術者試験 令和8年度 問2 ／ アルゴリズムとプログラミング › アルゴリズム
過去問にチャレンジ
クイックソートの処理方法を説明したものはどれか。
- ア
既に整列済みのデータ列の正しい位置に，データを追加する操作を繰り返していく方法である。
- イ
データ中の最小値を求め，次にそれを除いた部分の中から最小値を求める。この操作を繰り返していく方法である。
- ウ
適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
- エ
隣り合ったデータの比較と入替えを繰り返すことによって，小さな値のデータを次第に端の方に移していく方法である。
会話形式の解説
講師今回は整列アルゴリズムの説明を読み分ける問題です。それぞれの選択肢で、データをどんな単位で扱い、どの操作を繰り返しているかに注目すると区別しやすくなります。
受験者名前と手順がなかなか結び付かなくて、どれも「繰り返していく方法」と書いてあるので迷ってしまいます。
講師繰り返す操作の中身がそれぞれ違います。まず、整列済みのデータ列の正しい位置にデータを追加していく説明は、何をしているように読めますか。
受験者並んでいるところに1件ずつ差し込んでいく感じです。挿入ソートでしょうか。
講師そのとおりです。データを1件ずつ挿入して、整列済みの範囲を広げていく手順です。基準値でグループに分ける操作は入っていないので、クイックソートではありません。
受験者最小値を探して、残りからまた最小値を探す説明は、選択ソートだと思います。毎回最小値を選んで位置を決めているからです。
講師合っています。1回ごとに最小値を選んで位置を確定させるのが選択ソートです。こちらもデータをグループに分けてはいません。
受験者隣り合ったデータを比べて入れ替える説明はどうでしょうか。小さい値が端に移っていくので、これも少しずつ分けているように見えて迷います。
講師そこは確かめておきたい点です。この方法で比べる相手は隣のデータだけで、基準値を決めてグループに分けることはしていません。隣どうしの比較と入れ替えを繰り返すのは、バブルソート、別名の基本交換法です。
受験者すると残るのは、基準値を選んで、小さい値のグループと大きい値のグループに分ける説明ですね。
講師はい、それがクイックソートです。基準値はピボットとも呼びます。分けた各グループの中でも基準値を選んで同じように分割し、これを繰り返します。基準値で分割する点が、ほかの3つの方法と違うところです。
受験者整理すると、1件ずつ差し込むのが挿入ソート、最小値を選んで確定させるのが選択ソート、隣どうしを入れ替えるのがバブルソート、基準値で分けるのがクイックソート、ということですね。
講師よく整理できています。補足すると、クイックソートは問題を小さく分けて解く分割統治法の考え方に基づいています。平均の計算量は O(n log n) ですが、基準値の選び方が偏って分割の大きさに差が出ると、最悪で になります。
受験者基準値の選び方しだいで遅くなることもあるのですね。
講師そうです。もう一つ、一般的なクイックソートは、同じ値のデータの元の並び順を保つとは限りません。このような整列法を、安定でない整列法といいます。
まとめ
クイックソートは、基準値（ピボット）を選んでデータを小さい値のグループと大きい値のグループに分け、分けた各グループにも同じ分割を繰り返す整列法です。整列済みの部分へ1件ずつ挿入するのは挿入ソート、最小値を選んで順に確定させるのは選択ソート、隣り合うデータの比較と入れ替えを繰り返すのはバブルソート（基本交換法）です。見分けるときは、何を繰り返しているかに注目し、基準値で分割しているかどうかを確かめます。クイックソートの平均の計算量は O(n log n) ですが、分割が偏ると最悪で になり、一般的には安定でない整列法です。
解答・解説
正解はウです
この問題のテーマ
代表的な整列アルゴリズムの処理手順を読み分け、クイックソートに当たる説明を選ぶ問題です。
解き方の考え方
各選択肢で、データをどんな単位で扱い、どの操作を繰り返すかに注目します。整列済みの部分へ1件ずつ挿入する、最小値を選んで確定させる、隣どうしを比べて入れ替える、基準値で分割する、の4つに分けられます。このうち、基準値でグループを分け、分けた各グループに同じ処理を繰り返すものがクイックソートです。
選択肢ごとの解説
- ×ア 既に整列済みのデータ列の正しい位置に，データを追加する操作を繰り返していく方法である。アは、整列済みのデータ列の中の正しい位置に新しいデータを入れていく説明です。データを1件ずつ挿入して整列済みの範囲を広げる手順なので、挿入ソートに当たります。基準値でグループに分ける操作が含まれていないため、クイックソートではありません。
- ×イ データ中の最小値を求め，次にそれを除いた部分の中から最小値を求める。この操作を繰り返していく方法である。イは、最小値を探して取り出し、残りの部分から再び最小値を探す説明です。1回ごとに最小値を選んで位置を確定させる手順なので、選択ソートに当たります。データをグループに分ける操作がないため、クイックソートの説明にはなりません。
- ○ウ 適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。ウは、基準値を選んで、それより小さい値のグループと大きい値のグループにデータを分ける説明です。分けた各グループでも基準値を選んで同じように分割を繰り返しており、これはクイックソートの手順そのものです。分割したグループに同じ処理を再帰的に行う点が、ほかの3つの方法と違うところです。
- ×エ 隣り合ったデータの比較と入替えを繰り返すことによって，小さな値のデータを次第に端の方に移していく方法である。エは、隣り合う2つのデータを比べて入れ替える操作を繰り返し、小さい値を端へ移していく説明です。これはバブルソート（基本交換法）の手順です。比べる相手が隣のデータに限られ、基準値による分割はしていないため、クイックソートではありません。
補足
クイックソートは、問題を小さく分けて解く分割統治法の考え方に基づいています。平均の計算量は O(n log n) ですが、基準値の選び方が偏って分割の大きさに差が出ると、最悪で になります。また、一般的なクイックソートは、同じ値のデータの元の並び順を保つとは限らない（安定でない）整列法です。
POINT
- クイックソートでは、基準値（ピボット）を選んで小さい群と大きい群に分け、各群に同じ処理を再帰的に繰り返します。
- 挿入ソートは、整列済みの部分の正しい位置へデータを1件ずつ挿入していく方法です。
- 選択ソートは、残りの部分から最小値（または最大値）を選んで順に確定させる方法です。
- バブルソート（基本交換法）は、隣り合うデータの比較と入れ替えを繰り返す方法です。