選択アルゴリズム

@see http://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0#.E3.83.91.E3.83.BC.E3.83.86.E3.82.A3.E3.82.B7.E3.83.A7.E3.83.B3.E3.83.99.E3.83.BC.E3.82.B9.E3.81.AE.E6.B1.8E.E7.94.A8.E9.81.B8.E6.8A.9E.E3.82.A2.E3.83.AB.E3.82.B4.E3.83.AA.E3.82.BA.E3.83.A0
ソートされていない配列のind番目(0-base)の値を、
クイックソートを一部だけやって求める。
ピボットを適当に選んでるので実行時間はO(log N)~O(N^2)

by uwi 15 Oct 2009

Embed

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/7vBy
 */

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0#.E3.83.91.E3.83.BC.E3.83.86.E3.82.A3.E3.82.B7.E3.83.A7.E3.83.B3.E3.83.99.E3.83.BC.E3.82.B9.E3.81.AE.E6.B1.8E.E7.94.A8.E9.81.B8.E6.8A.9E.E3.82.A2.E3.83.AB.E3.82.B4.E3.83.AA.E3.82.BA.E3.83.A0
    // ソートされていない配列のind番目(0-base)の値を、
    // クイックソートを一部だけやって求める。
    // ピボットを適当に選んでるので実行時間はO(log N)~O(N^2)
    public class Test extends Sprite {
        private var _tf : TextField;
  
        public function Test() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            
            var N : int = 100000;
            
            var a : Array = new Array(N);
            var i : int;
            for(i = 0;i < N;i++)a[i] = i;
            shuffle(a); 
            
            var s : int = getTimer();
            tr(select(a, 2009));
//            a.sort();
            
            var g : int = getTimer();
            tr((g - s) + " ms");
        }
        
        private function select(a : Array, k : int, left : int = 0, right : int = -1) : *
        {
            if(right == -1)right = a.length;
            while(true){
                tr(k, left, right);
                var pnind : int = partition(a, left, right, Math.random() * (right - left) + left);
                if(k == pnind)return a[k];
                if(k < pnind){
                    right = pnind;
                }else{
                    left = pnind + 1;
                }
            }
            return null;
        }
        
        private function partition(a : Array, left : int, right : int, pind : int) : int
        {
            var n : int = a.length;
            var pv : * = a[pind];
            a[pind] = a[right - 1];
            a[right - 1] = pv;
            
            var sind : int = left;
            for(var i : int = left;i < right - 1;i++){
                if(a[i] <= pv){
                    var d : int = a[sind];
                    a[sind] = a[i];
                    a[i] = d;
                    sind++;
                }
            }
            a[right - 1] = a[sind];
            a[sind] = pv;
            return sind;
        }

        private function shuffle(a : Array) : void
        {
            var n : int = a.length;
            for(var i : int = 0;i < n - 1;i++){
                var t : int = Math.random() * (n - i - 1) + i + 1;
                var d : int = a[i];
                a[i] = a[t];
                a[t] = d;
            }
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
        }
    }
}