クイックソート(quick sort)

クイックソートは C. A. R. Hoare が 1962年に考案した比較と交換を 用いた整列法です. 配列する対称が巨大すぎて主記憶の中に入り切らない 等の特別な事情が無い場合, 平均的な実行効率が最もよい整列法として 知られています. 上で述べたように, クイックソートは汎用性がありますので, どのようなデータに対しても, 全順序を決めれば整列が実行できます. ただし, データを主記憶において整列しますので, それを上回る量のデータの ソートはできません.