Quicksort
US版wikipediaのタイトルが「Quick Sort」ではなく「Quicksort」なのでそれに合わせているmrsekut.icon
配列中から基準となる要素を選び、それより大きいもの、小さいもののリストを作っていき結合する
pivot値が要素全体の中央値に近い場合$ O(n \log n)
これが理想
だが、pivot値に最大値や最小値を取ると$ O(n^2)まで落ちる
これが最悪
つまりpivotのとり方がミソになる
命名
他のSortと比べて速いから"Quick"
新幹線に「ひかり」と命名する感じか？mrsekut.icon
計算量
平均計算時間: $ O(n \log{n})
最良計算時間: $ O(n\log{n})
常に配列要素の中央値をpivotに選択した場合
最悪計算時間: $ O(n^2)
毎回、pivotに最大値や最小値を選択した場合
雑に書くと、
Quicksortの計算量を$ T(n)とすると、
要素数が1個のときは、$ T(1)=O(n)
要素数がn個のときは、
pivotを選択した後、2つのリストに分ける$ O(n-1)
片方ずつ再帰する$ T(\frac{n-1}{2})
だから、$ T(n)=2T(\frac{n-1}{2})+O(n-1)
アルゴリズム
ピボットを選択
ピボットより大きいもの全てと、より小さいもの全ての配列に2分割する
というのを繰り返す
可視化
https://www.youtube.com/watch?v=8hEyhs3OV1w
https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif https://en.wikipedia.org/wiki/Quicksort
最右の要素をピボットとして選択している
コード例
code:hs
qsort [] = []
qsort (x:xs) = qsort lt ++ x ++ qsort gte where
code:ts
function qsort(arr: number[]): number[] {
if (arr.length === 0) return [];
const lt = xs.filter(n => n < pivot);
const gte = xs.filter(n => n >= pivot);
}
両者とも配列の先頭要素をpivotにしたmrsekut.icon
このページのhistoryを見ると2019/9頃に書いた(?)TSの謎コードがあったmrsekut.icon
プログラミング力の高まりを感じるmrsekut.icon
pivotの選択の例
先頭の要素にする
ランダムに1つ選ぶ
先頭、中央、末尾などのような3点を選んでその中央値を選択する
etc.
派生とか
その選択法によるQuicksortに対して、新たなSort名が付けられているものもある
速いだけなら「常にそれ使えば良いじゃん」になる
何かしらメリデメがあるはず
「実装が難しい」とかも理由に上がったりするのか？
参考
日本語のページより情報量がかなり多い