クイックソート
#ソートアルゴリズム
手順
ピボットをランダムに選ぶ
ピボット未満、ピボット、ピボット以上に分割する
要素が一つになるまで繰り返す
全て統合する
概要
ピボットによって分割する工程は必ず線形の計算量がかかる
ピボットによって毎回2分割できるとするとlogn回分割が行われることになる
よって実行時間は線形対数になる
常に最小の値をピボットに選んでしまうと言う最悪のシナリオでは分割できない→実質選択ソートになる
実用上は最も(マージソート、ヒープソートよりも)速いソート
分割統治
分割の工程で労力を支払っている
ピボットの選び方が重要である
とりあえず先頭の値をピボットにする等の実装ではデータに偏りがあった場合などに遅くなる
table:性能
計算量 O(nlogn)
安定ソート ❌
内部ソート ⭕️