部分ソート(3)

　実際の応用では、上記の(1),(2)の方法で十分な事が多いと思われる。しかしまぁ、他の方法も見てみよう。
　3つ目の方法は、quickselectを使う方法である。quickselectは、配列のk番目の要素を少ないコストで見付けるアルゴリズムだ。配列のk番目を見付けたければ、配列をquicksortしてからk番めにアクセスしても良い訳だが、全部をソートするのは明らかに無駄である。
　quickselectは、quicksortで不要な部分のソートをサボりながらk番目の要素を見付ける、と表現すると、直感的にはわかりやすいかもしれない。
　quicksortはpivotを選択して、そのpivotの値よりも大きいか小さいかで要素を分ける（この操作をpartitionと呼んでおこう）という操作を再帰的に繰り返すことによってソートを行う。しかし、k番目の要素が見付けたいだけであるなら、以下のようにすると計算をサボれる。

  if(length(left_partition) == k ) {
    return last(left_partition);
  } else if(length(left_partition) > k ) {
    return quickselect(left_partition, k);
  } else {
    return quickselect(right_patition, k - length(left_partition));
  }

　quickselectを行うと、k番目の要素と、それよりも小さなk-1個の要素が手に入る。このk-1個の要素はソートされていないので、quicksortとかでソートしてやれば、部分ソートが行える。段々眠くなってきたので計算は省くけれど、quickselectの平均計算量はnであるらしい。（ついでに、最悪はn^2。）
　最後のソートは明らかにm log mであるので、この場合の計算量はn + m log mになる。n log nと比べると、それなりに魅力的になったのではないだろうか。
　実はこの話には元ネタとなるファイルがあって、しかもさらに続きがある（が理解できなかったので省略した）ので、興味のある人は「On Partial Sorting」とか「chunksort」とかでぐぐるといいかもしれない。