AS3 sorting algorithm faster than native sorting

AS3 sorting algorithm faster than native sorting
クリックでストップ、再度クリックでスタート。
via : http://www.valveblog.com/2009/06/as3-sorting-algorithm-faster-than-native-sorting.html

by bkzen 20 Jun 2009

• Related works: 2

Tags

benchmark sort 最適化
Embed

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

package
{
    import flash.display.Sprite;
    import flash.display.StageAlign;
    import flash.display.StageScaleMode;
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.text.TextField;
    import flash.utils.getTimer;
    
    /**
     * AS3 sorting algorithm faster than native sorting
     * クリックでストップ、再度クリックでスタート。
     * via : http://www.valveblog.com/2009/06/as3-sorting-algorithm-faster-than-native-sorting.html
     */
    public class Sorting extends Sprite 
    {
        private var txt: TextField;
        private var tgr: Boolean = true;
        public function Sorting() 
        {
            if (stage) init();
            else addEventListener(Event.ADDED_TO_STAGE, init);
        }
        
        private function init(e: Event = null): void 
        {
            removeEventListener(Event.ADDED_TO_STAGE, init);
            
            stage.align = StageAlign.TOP_LEFT;
            stage.scaleMode = StageScaleMode.NO_SCALE;
            txt = new TextField();
            txt.width = stage.stageWidth > 0 ? stage.stageWidth : 465;
            txt.height = stage.stageHeight > 0 ? stage.stageHeight : 465;
            addChild(txt);
            addEventListener(Event.ENTER_FRAME, loop);
            stage.addEventListener(MouseEvent.CLICK, onClick);
        }
        
        private function onClick(e:MouseEvent):void 
        {
            if (tgr) removeEventListener(Event.ENTER_FRAME, loop);
            else addEventListener(Event.ENTER_FRAME, loop);
            tgr = !tgr;
        }
        
        private function loop(e: Event): void 
        {
            trc();
            var data:Vector.<Number> = new Vector.<Number>();
            for(var i:int = 0; i<10000; i++){
                data.push(Math.random()*10000);
            }
            var data2:Vector.<Number> = data.concat();
            var t:Number = getTimer();
            data.sort(sf);
            trc("Native sort", (getTimer()-t));
            t = getTimer();
            data.sort(sf);
            trc("Native sort on ordered elements", (getTimer()-t));
            t = getTimer();
            shellSort(data2);
            trc("AS3 Shell sort", (getTimer()-t));
            t = getTimer();
            shellSort(data2);
            trc("AS3 Shell sort on ordered elements", (getTimer()-t));
        }
        
        private function trc(... args): void
        {
            if (args.length == 0) txt.text = "";
            else txt.appendText(args + "\n");
        }
        
        final private function sf(a: Number, b: Number): int 
        {
            return (a==b ? 0 : (a < b) ? -1 : 1);
        }
        
        final private function shellSort(data: Vector.<Number>): void 
        {
            var n:int = data.length;
            var inc:int = int(n/2);
            while(inc) {
                for(var i:int=inc; i<n; i++) {
                    var temp:Number = data[i], j:int = i;
                    while(j >= inc && data[int(j - inc)] > temp) {
                        data[j] = data[int(j - inc)];
                        j = int(j - inc);
                    }
                    data[j] = temp
                }
                inc = int(inc / 2.2);
            }
        }
    }
}