スポンサーサイト

-------- | --:--

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[ActionScript 3.0] Fisher-Yatesアルゴリズムの可視化

2008-01-17 | 20:46

要素をランダムに並べ替えるFisher-Yatesというアルゴリズムを可視化してみた。
下のウィンドウをマウスクリックすると並び替えの様子がアニメーションされます。

後ろから走査していって、自分より前のどれかと交換していく訳ですね。
計算量はO(n)です。

package{
        import flash.display.*;
        import flash.events.*;
        import flash.geom.*;
        import flash.utils.*;
        
        import caurina.transitions.Tweener;
        
        [SWF(width="400", height="200",backgroundColor="0xffffff")]
        
        
        public class FisherYates2 extends Sprite{
                
                private var balls:Array = [];
                private var processing:Boolean = false;
                
                private var Y:int = 100;
                private var INTERVAL:int = 10;
                
                private var RADIUS:int = 4;
                public function FisherYates2(){
                        
                        for(var i:int = 0 ; i < 40 ; i++){
                                
                                var c:int = ((i*5) << 16) + ((i*5) << 8);
                                var b:Ball = new Ball(c,RADIUS);
                                
                                balls.push(b);
                                addChild(b);
                                b.x = i*INTERVAL+RADIUS;
                                b.y = Y;
                        }
                        
                        stage.addEventListener(MouseEvent.MOUSE_DOWN, mouseDown);
                        
                }
                
                // シャッフルして並び替え手順を記録
                private function shuffle(i:int) : void{
                        
                        if(i > 0){
                                var j:int = Math.floor(Math.random() * (i + 1));
                                
                                
                                // 並び替えをアニメーション
                                var b:Ball = balls[i];
                                
                                Tweener.addTween(b, {x:j*INTERVAL+RADIUS, y:Y,
                                                         _bezier:[{x:i*INTERVAL+RADIUS, y:Y-20}, {x:j*INTERVAL+RADIUS, y:Y-20},],
                                                         time:1, transition:"linear"} );
                                
                                b = balls[j];
                                Tweener.addTween(b, {x:i*INTERVAL+RADIUS, y:Y,
                                                         _bezier:[{x:j*INTERVAL+RADIUS, y:Y+20}, {x:i*INTERVAL+RADIUS, y:Y+20},],
                                                         
                                        time:1, transition:"linear",
                                                         onComplete:function():void{shuffle(--i)}});
                                
                                
                                if(i != j){
                                        
                                        // 中身を並び替える
                                        
                                        var ball:Ball= balls[i];
                                        balls[i] = balls[j];
                                        balls[j] = ball;
                                        
                                }
                        }else
                        processing = false;
                        
                }
                
                private function mouseDown(e:Event):void{
                        
                        if(processing)
                        return;
                        processing = true;
                        
                        // シャッフル
                        shuffle(balls.length-1);
                }
        }
}

import flash.display.*;

internal class Ball extends Sprite{
        
        public function Ball(color:int, radius:int){
                
                graphics.beginFill(color);
                graphics.drawCircle(0,0,radius);
                graphics.endFill();
        }
}


スポンサーサイト
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。