クイックソートの処理方法を他の整列法と見分けるには
基本情報技術者試験 平成30年度秋期 午前 問6 ／ アルゴリズムとプログラミング › アルゴリズム
過去問にチャレンジ
クイックソートの処理方法を説明したものはどれか。
- ア
既に整列済みのデータ列の正しい位置に，データを追加する操作を繰り返していく方法である。
- イ
データ中の最小値を求め，次にそれを除いた部分の中から最小値を求める。この操作を繰り返していく方法である。
- ウ
適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
- エ
隣り合ったデータの比較と入替えを繰り返すことによって，小さな値のデータを次第に端の方に移していく方法である。
会話形式の解説
講師今回は整列アルゴリズム、つまりデータを順番に並べる手順の説明文を読み比べて、クイックソートを選ぶ問題です。選択肢ごとに「何を手がかりに並べているか」を一言でまとめてみると見分けやすくなります。
受験者名前は覚えているのですが、どれがどの手順だったかがあいまいです。クイックソートは名前の通り速い方法、という印象しかありません。
講師では一つずつまとめましょう。最初の選択肢は「整列済みのデータ列の正しい位置にデータを追加する」です。何をしている手順でしょうか。
受験者すでに並んでいる部分に差し込んでいくので、挿入ソートだと思います。
講師その通りです。挿入ソート（基本挿入法）の説明で、基準値を選ぶ操作もグループに分ける操作も出てきません。次の「最小値を求め、それを除いた部分から最小値を求める」はどうでしょう。
受験者最小値を選び出すので選択ソートですね。ただ、残りの部分とそれ以外に分けているとも読めて、分割と言えなくもない気がしました。
講師そこは紛らわしいところです。選択ソート（基本選択法）で毎回取り出すのは最小値の1個だけです。基準値より小さいグループと大きいグループの二つに分けているわけではないので、クイックソートの分割とは違います。
受験者なるほど。1個ずつ取り出すのと、二つのグループに分けるのとでは中身が違うのですね。最後の「隣り合ったデータの比較と入替え」はバブルソートでしょうか。
講師はい、バブルソート（基本交換法）です。比べる相手は常に隣のデータで、小さな値が少しずつ端へ移っていきます。基準値による分割はありません。
受験者残るのは、基準値を選んで小さい値と大きい値のグループに分け、それぞれのグループでも同じことを繰り返す説明です。これがクイックソートですね。
講師正解です。クイックソートの目印は二つあります。基準値（ピボット）を選んでデータを二つのグループに分けること、そして分けた後の各グループにも同じ手順を当てはめることです。グループが十分小さくなるまで続けると全体が整列します。
受験者選択肢では「基準値」と「分割」という言葉を探せばよい、ということですね。分割を繰り返す部分はプログラムではどう書くのですか。
講師分けたグループに同じ処理を当てはめるので、自分自身を呼び出す再帰呼び出しで実現するのが一般的です。また、クイックソートは平均の計算量がO(n log n)で多くの場合に高速ですが、基準値が最大値や最小値に偏り続けると分割がうまく進まず、まで遅くなります。名前の印象だけで「いつも速い」と覚えないように注意しましょう。
まとめ
クイックソートは、基準値（ピボット）を選んでデータを小さい値と大きい値の二つのグループに分け、各グループでも同じ分割を繰り返す整列法です。整列済みの部分へ差し込むのは挿入ソート、最小値を選び出すのは選択ソート、隣同士を入れ替えるのはバブルソートです。選択ソートは最小値を1個ずつ取り出すだけで、二つのグループへの分割ではない点で区別できます。選択肢では「基準値」「分割」という語句が見分ける手がかりになります。平均計算量はO(n log n)ですが、基準値が偏り続けるとまで遅くなります。
解答・解説
正解はウです
この問題のテーマ
代表的な整列アルゴリズムの説明文を読み比べて、クイックソートの説明を選ぶ問題です。
解き方の考え方
各選択肢が何を手がかりにデータを並べているかに注目します。挿入する、最小値を選ぶ、基準値で分ける、隣と入れ替える、という操作の違いがそのままアルゴリズムの違いになります。クイックソートの目印は、基準値を選んでデータを二つのグループに分けることと、分けた後のグループにも同じ手順を当てはめることの二点です。この二点がそろっている選択肢を選びます。
選択肢ごとの解説
- ×ア 既に整列済みのデータ列の正しい位置に，データを追加する操作を繰り返していく方法である。アは、すでに並んでいる部分の正しい位置へデータを差し込む方法を説明しています。これは挿入ソート（基本挿入法）の手順です。基準値を選ぶ操作もグループに分ける操作も含まれていないため、クイックソートではありません。
- ×イ データ中の最小値を求め，次にそれを除いた部分の中から最小値を求める。この操作を繰り返していく方法である。イは、残りの部分から最小値を選び出す操作を繰り返す方法です。これは選択ソート（基本選択法）にあたります。毎回取り出すのは最小値の1個だけで、データを二つのグループに分けてはいないので、クイックソートとは異なります。
- ○ウ 適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。ウのように基準値（ピボット）を選んでデータを小さい値と大きい値のグループに分け、それぞれのグループでも同じ分割を繰り返す方法は、クイックソートの手順そのものです。グループが十分小さくなるまで分割を続けると、全体が整列した状態になります。
- ×エ 隣り合ったデータの比較と入替えを繰り返すことによって，小さな値のデータを次第に端の方に移していく方法である。エは、隣り合う二つのデータを比べて入れ替える操作を繰り返し、小さな値を少しずつ端へ移す方法です。これはバブルソート（基本交換法）にあたります。比べる相手は常に隣のデータで、基準値による分割は行わないので、クイックソートではありません。
補足
クイックソートは多くの場合に高速で、平均の計算量はO(n log n)です。ただし、基準値が最大値や最小値に偏り続けると分割がうまく進まず、まで遅くなります。この遅くなる条件も、計算量を問う問題で出題されることがあります。
POINT
- クイックソートは、基準値（ピボット）を選んでデータを二つのグループに分け、各グループで同じ分割を繰り返す整列法です。
- 分けたグループに同じ処理を当てはめる繰り返しは、再帰呼び出しで実現するのが一般的です。
- 整列済みの部分へ差し込むのは挿入ソート、最小値を選び出すのは選択ソート、隣同士を入れ替えるのはバブルソートです。
- 選択肢では「基準値」「分割」という語句がクイックソートを見分ける手がかりになります。