ITパスポート 試験情報＆徹底解説

ソートアルゴリズムの一つで、1960年にイギリスのコンピュータ科学者アントニー・ホーアが考案したもの。一般的に最も高速なソートアルゴリズムだとされているが、データの並びなどによっては最速ではない場合もある。

具体的な手順は、データのなかから任意の基準値を選び、基準値より大きいグループと小さいグループに分ける。2つのグループに対して、改めて基準値を選び、基準値より大きいグループと小さいグループに分ける。この作業をグループが1になるまで繰り返す。このようにグループを分割して処理しやすくする手法を分割統治法という。

基準値の選び方で比較回数が変わる。一般的にはデータの中央値を基準にすれば速くなるが、基準値の選び方を複雑にするとその部分で処理が遅くなるため、機械的に最初の要素にしたりランダムに選んだりすることも多い。