クイックソートはピボットの選び方の違いで平均計算量に違いが出るそう。
今回実装したのは、部分配列の先頭をピボットにするという安易な方法。
あんまQUICKじゃな・・
def quick_sort(a, l, r)
return if l >= r
pivot = a[l]
ll = l
rr = r
loop do
ll += 1 while a[ll] < pivot
rr -= 1 while a[rr] > pivot
break if ll >= rr
a[ll], a[rr] = a[rr], a[ll]
ll += 1
rr -= 1
end
quick_sort(a, l, rr)
quick_sort(a, rr + 1, r)
end
ざっくりと説明。
１．ピボットなる値を求める。この実装では適当に部分配列の先頭をピボットにしている（4行目）
２．部分配列の左からピボット以上の値が出てくる位置を探す。（８行目）
３．部分配列の右からピボット以下の値が出てくる位置を探す。（９行目）
４．２と３の値を入れ替える（１３行目）
５．その部分配列での処理を終えたら、ピボットの位置の左側と右側を部分配列として再帰（１８，１９行目）
