問題 No.2236
基準となるデータ（ピボット）を一つ選び、それよりも小さな値を左側に、大きな値を右側にグループ分けすることを再帰的に繰り返して全体を高速に並び替える整列アルゴリズムはどれか。
【正解の解説】
クイックソート（分割統治法）
クラスの背の順を並び替えるとき、適当に選んだ一人の基準を真ん中に置いて「自分より背が低い人は左へ、高い人は右へ」とグループをパパッと分ける作業を、小グループに分かれて全員が完了するまで同時並行で繰り返すイメージです。この効率的な仕分け方により、データ数が多くても一気に高速で綺麗に並べ替えることができます。
スポンサーリンク
【その他の選択肢の解説】
マージソート（分割統治法）
クイックソートが「基準を先に決めて左右に分ける」アプローチであるのに対し、マージソートは「何も考えずにまず半分にバキッと割り、最後に順番を合わせながらキレイに糊付けしていく」というアプローチをとります。どちらも分割統治法という大きな仲間ですが、仕分けのタイミングが真逆である点に注意が必要です。
バブルソート（隣接交換法）
水中の泡がボコボコと上へ浮き上がるように、端から順に隣同士のペアを比べて大きい方を右へ送る動作を何周も繰り返します。仕組みが直感的で分かりやすい反面、データ量が増えるともの凄く時間がかかるため、一気にグループ分けして爆速で片付けるクイックソートとは効率面で大きな違いがあります。
ヒープソート（木構造利用）
データ全体をトーナメント戦の勝ち抜き表のようなツリー構造に見立てて、常に一番大きな値を根っこから引っこ抜いていくことで並び替えます。ピボットを使ってグループをスパッと二分割していくクイックソートとは異なり、木構造の親子関係を管理しながら整列を進める点が決定的な違いです。