クイックソートくいっくそーと

クイックソート（Quick Sort）は、ピボット（基準きじゅん値ち）を 1 つ選えらび、それより小ちいさい要素ようそと大おおきい要素ようそに分割ぶんかつして、それぞれを 再帰さいき（再帰さいき）で同様どうようにソートする分割ぶんかつ統治とうち型がたのアルゴリズムです。

観点かんてん	クイックソート
平均へいきん計算けいさん量りょう	$O(N\log N)$
最悪さいあく計算けいさん量りょう	$O\left(N^2\right)$
仕組しくみ	ピボットで分割ぶんかつ→再帰さいき
特徴とくちょう	平均へいきん的てきに最速さいそく級きゅう・追加ついかメモリ少しょう

たとえばピボットに中央ちゅうおう付近ふきんの値ねを選えらぶと、左右さゆうがほぼ均等きんとうに分わかれて効率こうりつよくソートできます。平均へいきんでは実用じつよう最速さいそく級きゅうですが、すでに整列せいれつ済ずみのデータでピボット選択せんたくが偏かたよると最悪さいあく$O\left(N^2\right)$ になります。多おおくの標準ひょうじゅんライブラリで採用さいようされる定番ていばんソートです。

試験しけんでは 「ピボットで分割ぶんかつ」「平均へいきん$O(N\log N)$・最悪さいあく$O\left(N^2\right)$」と、マージソート との違ちがい（安定あんてい性せい・メモリ）が問とわれます。