ソートの比較

クイックソートだけ交換ソートじゃなかったり色々するので比較はあまりできないかもしれない
ソートしているのは円周率上位40000桁を4つずつ区切ったもの
コムソートは9,10のとき11にするようなのにしてある
そして関数外部の変数へのアクセスが若干遅いのでカウンタを取っ払えばもう少し速い
クイックソートが遅いのは再帰呼び出しが遅いせいだと信じている

by Susisu 23 Jan 2011

Embed

package {
    import flash.text.TextField;
    import flash.events.Event;
    import flash.net.URLRequest;
    import flash.net.URLLoader;
    import flash.display.Sprite;
    public class FlashTest extends Sprite {
        private var pi:Vector.<int>;
        private var loader:URLLoader=new URLLoader();
        private var tf:TextField=new TextField();
        private var lc:int=0,sc:int=0;
        public function FlashTest() {
            tf.width=tf.height=465;
            tf.text="wait...";
            addChild(tf);
            loader.addEventListener(Event.COMPLETE,loaded);
            loader.load(new URLRequest("http://susisu.ktkr.net/pi.txt"));
        }
        private function loaded(e:Event):void{
            loader.removeEventListener(Event.COMPLETE,loaded);
            var t:Array=loader.data.split(",");
            pi=new Vector.<int>();
            var l:int=t.length;
            for(var i:int=0;i<l;i++){
                pi.push(int(t[i]));
            }
            tf.text="loaded\n"+l.toString()+" items\n";
            test();
        }
        private function test():void{
            tf.appendText("start tests\n\n");
            var sorts:Array=["bubble","gnome","comb","quick"];
            var l:int=sorts.length;
            for(var i:int=0;i<l;i++){
                tf.appendText(sorts[i]+"\n");
                lc=0;
                sc=0;
                var s:Date=new Date();
                //tf.appendText(this[sorts[i]](pi).toString()+"\n");
                this[sorts[i]](pi.slice());
                var e:Date=new Date();
                tf.appendText(lc.toString()+" loops\n");
                tf.appendText(sc.toString()+" swaps\n");
                tf.appendText((e.time-s.time).toString()+"ms\n\n");
            }
        }
        private function bubble(vec:Vector.<int>):Vector.<int>{
            var l:int=vec.length;
            for(var i:int=0;i<l;i++){
            for(var j:int=0;j<i;j++){
                    if(vec[i]<vec[j]){
                        var t:int=vec[i];
                        vec[i]=vec[j];
                        vec[j]=t;
                        sc++;
                    }
                    lc++;
                }
            }
            return vec;
        }
        private function gnome(vec:Vector.<int>):Vector.<int>{
            var l:int=vec.length;
            var i:int=1;
            while(i<l){
                var n:int=i-1;
                if(vec[n]<=vec[i])i++;
                else{
                    var t:int=vec[n];
                    vec[n]=vec[i];
                    vec[i]=t;
                    i--;
                    if(i==0)i+=2;
                    sc++;
                }
                lc++;
            }
            return vec;
        }
        private function comb(vec:Vector.<int>):Vector.<int>{
            var l:int=vec.length;
            var h:int=l/1.3>>0;
            while(1){
                if(h==9||h==10)h=11;
                var s:int=0;
                for(var i:int=0;i+h<l;i++){
                    var n:int=i+h;
                    if(vec[i]>vec[n]){
                        var t:int=vec[i];
                        vec[i]=vec[n];
                        vec[n]=t;
                        s++;
                        sc++;
                    }
                    lc++;
                }
                if(h==1){
                    if(s==0)break;
                }
                else h=h/1.3>>0;
            }
            return vec;
        }
        private function quick(vec:Vector.<int>):Vector.<int>{
            var n:int=vec.length;
            if(n==0)return vec;
            var p:uint=vec[0];
            var l:Vector.<int>=new Vector.<int>();
            var r:Vector.<int>=new Vector.<int>();
            for(var i:int=1;i<n;i++){
                if(vec[i]<=p)l.push(vec[i]);
                else r.push(vec[i]);
                lc++;
            }
            l=arguments.callee(l);
            r=arguments.callee(r);
            l.push(p);
            return l.concat(r);
        }
    }
}