教科書で学ぶ探索と整列のアルゴリズム
定義クイックソートは、基準値 (ピボット) を 1 つ決めてデータをそれより小さい組と大きい組に分け、各組にも同じ手順を繰り返す整列法である。
解説組の要素が 1 個以下になれば分ける必要がなくなり、各組を順に並べると全体が整列する。このように、同じ手順をより小さな部分に当てはめていくやり方を再帰という。平均的な比較回数は件数の 2 乗型の方法より少ないが、基準値の選び方が悪いと件数の 2 乗に近づく。
たとえ書類の山を基準の日付より前の山と後の山に分け、それぞれの山をまた同じように分けていくようなもの。
記憶フックquick は英語で「速い」の意味。