- 358 名前：卵の名無しさん mailto:sage [2018/08/12(日) 08:49:17.88 ID:vzhZWzVW.net]
- >>266
https://www.youtube.com/watch?v=Hoixgm4-P4M
に従ってpivotの選び方をmedian of threeにしてみた
med3 <- function(x){ # median of three(first, middle, last)
y=c(x[1],x[(length(x)/2)],x[length(x)])
mid=y[c(y[1]>=min(y[2],y[3])&y[1]<=max(y[2],y[3]),
y[2]>=min(y[3],y[1])&y[2]<=max(y[3],y[1]),
y[3]>=min(y[1],y[2])&y[3]<=max(y[1],y[2]))]
return(mid)
}
quicksort3 <- function (x) {
if (length(x) <= 1) return(x)
if (length(x) == 2) {
if (x[1] <= x[2]) return(x)
else return(x[2:1])
}
pivot=med3(x) # instead of pivot=sample(x,1)
return( c(quicksort3(x[x < pivot]), x[x == pivot], quicksort3(x[x > pivot])) )
}
結果は、ランダム抽出でのpivotにボロ負け
> system.time(quicksort3(1e6:1))
user system elapsed
15.90 0.03 15.96
> system.time(quicksort(1e6:1))
user system elapsed
4.10 0.02 4.13
|
 |
