Forked from:: matacat's ff: [betweenAS3]BubbleSort And SelectionSort

Miracle Bogo Sort

/*
BogoSortとは？
ボゴソート (英語: bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。
ボゴソートは、「量子ボゴダイナミックス」というユーモラスな用語にちなんで名付けられている。その元は、bogus（偽の）である。英語では、 random sort, shotgun sort, monkey sort ともいう。

アルゴリズム
トランプを順に並べる場合を例にすると、次のようになる。

1. トランプ52枚の束を放り投げて、ばらばらにする。
2. 1枚ずつ無作為にすべてを拾い集める。
3. ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。

カードをシャッフルし続けて、偶然一列に並ぶのをひたすら待ちつづけるアルゴリズムと考えてもよい。

wikipediaより
　

計算量O(n×n!)をなめんな！！

matsu4512

forked:2
favorite:12
lines:245
license : MIT License
modified : 2010-04-19 22:25:18

Embed: Tweet

// forked from matacat's ff: [betweenAS3]BubbleSort And SelectionSort
// forked from applicott's [betweenAS3]BubbleSort And SelectionSort

// forked from matacat's ff: [betweenAS3]BubbleSort And SelectionSort
// forked from applicott's [betweenAS3]BubbleSort And SelectionSort
/*
/*
BogoSortとは？
ボゴソート (英語: bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。
ボゴソートは、「量子ボゴダイナミックス」というユーモラスな用語にちなんで名付けられている。その元は、bogus（偽の）である。英語では、 random sort, shotgun sort, monkey sort ともいう。

アルゴリズム
トランプを順に並べる場合を例にすると、次のようになる。

1. トランプ52枚の束を放り投げて、ばらばらにする。
2. 1枚ずつ無作為にすべてを拾い集める。
3. ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。

カードをシャッフルし続けて、偶然一列に並ぶのをひたすら待ちつづけるアルゴリズムと考えてもよい。

wikipediaより

計算量O(n×n!)をなめんな！！

*/
package
{
	import com.bit101.components.Label;
	import com.bit101.components.PushButton;
	import com.bit101.components.Text;
	
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.MouseEvent;
	import flash.net.URLRequest;
	import flash.net.navigateToURL;
	import flash.utils.escapeMultiByte;
	
	import frocessing.color.ColorHSV;
	
	import org.libspark.betweenas3.BetweenAS3;
	import org.libspark.betweenas3.tweens.ITween;
	
	[SWF(backgroundColor = 0x000000, frameRate = 60, width=465, height=465)]
	
	public class BogoSort extends Sprite
	{
		// 配列に関する定数・変数
		private var NUM:uint;    // 配列の要素数
		private var list:Vector.<Bar>;  // 棒の配列
		private var curId:int;          // ソートに用いる。現在注目している要素など
		private var selId:int;          // ソートに用いる。比較対象の要素など
		
		// モーションに関する変数
		private var standby:Boolean;  // モーションが完了したかどうかのフラグ
		
		// 背景
		private var shuffleName:MotionName;

private var count:int=0;
		
		private var startBtn:PushButton;
		private var txt:Text;
		private var label:Label;
		
		
		public function BogoSort()
		{
			graphics.beginFill(0);
			graphics.drawRect(0,0,465,465);
			graphics.endFill();
			label = new Label(this, 140, 50, "Input Element Num");
			txt = new Text(this, 140, 80, "4");
			txt.width = 50;
			txt.height = 20;
			startBtn = new PushButton(this, 200, 80, "start", start);
		}
		
		private function start(e:MouseEvent):void{
			removeChild(startBtn);
			removeChild(label);
			removeChild(txt);
			
			NUM = int(txt.text);
			
			var wz:int = stage.stageWidth;
			var hi:int = stage.stageHeight;
			
			graphics.beginFill(0);
			graphics.drawRect(0, 0, wz, hi);
			
			MotionName.centerY = hi / 2;
			shuffleName = addChild(new MotionName("Bogo Sort")) as MotionName;
			
			// Bar クラスの初期設定
			Bar.centerY   = hi / 2;               // ステージ中央の Y 座標で棒の高さをそろえる
			Bar.interval  = wz / NUM;             // 棒の間隔はステージの幅を棒の総数で割った数
			Bar.lengthMin = 25;                   // 棒の長さの最小値
			Bar.lengthInc = (hi / 2 - 25) / NUM;  // 棒の長さの増分
			
			// リスト初期設定
			list = new Vector.<Bar>(NUM, true);
			var hsv:ColorHSV = new ColorHSV();
			for (var i:int = 0; i < NUM; i++) {
				list[i] = new Bar(i, hsv.toRGB().value);
				addChild(list[i]);
				hsv.h = 360*i/NUM;
			}
			
			getReady();
			
			stage.addEventListener(MouseEvent.CLICK, click);
		}
		
		
		private function click(e:MouseEvent):void
		{
			stage.removeEventListener(MouseEvent.CLICK, click);
			if (standby) {
				// モーション実行中に別のモーションを実行しないように
				standby = false;
				
				// モーション切り替え。名前を表示し、ソート（シャッフル）を実行する
				shuffleName.appear(); shuffle();
			}
		}
		
		
		private function getReady():void
		{
			// ソート（シャッフル）を実行する前の準備
			curId   = 0;
			selId   = 0;
			standby = true;
		}
		
		
		private function shuffle():void
		{
			// リストのシャッフル
			//   curId: 現在注目している要素。リストを前方から後方へ走査する
			//   selId: curId と交換する要素。 curId より前方の要素からランダムに選ぶ
			count++;
			while (++curId < NUM) {
				selId = Math.random() * curId >> 0;
				if (curId == selId) continue;
				
				var b:Bar   = list[curId];
				list[curId] = list[selId];
				list[selId] = b;
			}
			
			var tweens:Array = [];
			for (curId = 0; curId < NUM; curId++){
				tweens.push(list[curId].goto(curId));
			}
			var tween:ITween = BetweenAS3.parallelTweens(tweens);
			tween.onComplete = check;
			tween.play();
		}
		
		private function check():void{
			var pre:Number=0;
			for(var i:uint = 0; i < NUM; i++){
				if(pre <= list[i].height) pre = list[i].height;
				else break;
			}
			if(i==NUM) complete();
			else{ 
				getReady();
				shuffle();
			}
		}
		
		private function complete():void{
			removeChild(shuffleName);
			(addChild(new MotionName(count + "回でSort完了")) as MotionName).appear();
			var twitBtn:PushButton = new PushButton(this, 0, 0, "twitter", twitter);
			twitBtn.x = stage.stageWidth/2-twitBtn.width/2;
			twitBtn.y = stage.stageHeight/2;
		}
		
		private function twitter(e:MouseEvent):void{
			if(NUM < 5)
				navigateToURL(new URLRequest("http://twitter.com/home?status="+escapeMultiByte("あなたはN=" + NUM.toString() + "でボゴった結果、" + count + "回目の試行でSort完了しました。" + " #bogosorter  http://wonderfl.net/c/gT9W")));
			else
				navigateToURL(new URLRequest("http://twitter.com/home?status="+escapeMultiByte("あなたはN=" + NUM.toString() + "でボゴった結果、" + count + "回目の試行でSort完了しました。あなたは立派なボゴソーターです！おめでとう！！" + " #bogosorter  http://wonderfl.net/c/gT9W")));
		}
		
		private function sMotion(e:Event):void
		{
			if (++selId % 5 != 0) return;
			
			// 位置はそのままで配列だけをシャッフルしたので、
			// インデックスに対応した位置に移動させれば良い
			if (++curId < NUM - 1) {
				list[curId].goto(curId);
			} else if (curId == NUM - 1) {
				list[curId].goto(curId, getReady);
			} else {
				removeEventListener(Event.ENTER_FRAME, sMotion);
				shuffleName.disappear();
			}
		}
	}
}

import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Graphics;
import flash.display.Shape;
import flash.events.Event;
import flash.filters.BlurFilter;
import flash.geom.ColorTransform;
import flash.geom.Matrix;
import flash.geom.Point;
import flash.text.TextField;
import flash.text.TextFormat;

import org.libspark.betweenas3.BetweenAS3;
import org.libspark.betweenas3.easing.Bounce;
import org.libspark.betweenas3.easing.Elastic;
import org.libspark.betweenas3.easing.Quad;
import org.libspark.betweenas3.easing.Sine;
import org.libspark.betweenas3.tweens.ITween;

class Bar extends Bitmap
{
	private static const THICKNESS:int = 2;
	private static const EDGE:int      = 2;
	
	public static var centerY:Number;
	public static var interval:Number;
	public static var lengthMin:Number;
	public static var lengthInc:Number;
	public var length:Number;
	
	private var upT:ITween;
	private var downT:ITween;
	
	
	public function Bar(index:int, color:uint)
	{
		length = lengthMin + lengthInc * index;
		
		var totalThick:int = THICKNESS + EDGE * 2;
		var ofsX:Number    = interval / 2;
		var line:Shape     = new Shape();
		var g:Graphics     = line.graphics;
		
		g.lineStyle(totalThick, 0, 0.5, true);
		g.moveTo(ofsX, totalThick / 2);
		g.lineTo(ofsX, length);
		
		g.lineStyle(THICKNESS, color, 1, true);
		g.moveTo(ofsX, totalThick / 2);
		g.lineTo(ofsX, length);
		
		bitmapData = new BitmapData(interval, length + totalThick, true, 0);
		bitmapData.draw(line);
		
		x = index * interval;
		y = centerY - totalThick / 2;
		
		upT   = BetweenAS3.tween(this, { y: centerY - totalThick / 2 - length }, null, 0.4, Elastic.easeOut);
		downT = BetweenAS3.tween(this, { y: centerY - totalThick / 2 },          null, 0.8, Bounce.easeOut);
	}
	
	
	public function goto(index:Number, onComplete:Function = null):ITween
	{ 
		var slideT:ITween = BetweenAS3.tween(this, { x: index * interval }, null, 0.2, Quad.easeInOut);
		if (onComplete != null) slideT.onComplete = onComplete;
		
		return BetweenAS3.serial(
			BetweenAS3.parallel(
				upT,
				BetweenAS3.delay(slideT, 0.2)
			),
			downT
		);
	}
}

class MotionName extends Bitmap
{
	public static var centerY:Number;
	
	private var fadeIn:ITween;
	private var fadeOut:ITween;
	private var blink:ITween;
	
	
	public function MotionName(name:String)
	{
		var mx:Matrix = new Matrix();
		
		var tf:TextField     = new TextField();
		tf.defaultTextFormat = new TextFormat("_serif", 72, 0xFFFFFF);
		tf.autoSize          = "left";
		tf.text              = name;
		
		var wz:int = tf.width;
		var hi:int = tf.height * 0.9;
		
		mx.createGradientBox(wz, hi, Math.PI / 2);
		
		var gd:Shape = new Shape();
		gd.graphics.beginGradientFill("linear", [0, 0], [0, 0.8], [63, 255], mx);
		gd.graphics.drawRect(0, 0, wz, hi);
		
		var temp:BitmapData = new BitmapData(wz, hi, true, 0);
		temp.draw(tf);
		temp.draw(gd);
		temp.applyFilter(temp, temp.rect, new Point(), new BlurFilter(4, 4, 3));
		
		super(new BitmapData(wz, hi * 1.75, false, 0));
		bitmapData.draw(temp);
		mx.createBox(1, -0.75, 0, 0, hi * 1.75);
		bitmapData.draw(temp, mx, new ColorTransform(0.3, 0.3, 0.3));
		
		y     = centerY - hi;
		alpha = 0;
		
		temp.dispose();
		
		fadeIn  = BetweenAS3.tween(this, { alpha: 1.0 }, null, 1, Sine.easeInOut);
		fadeOut = BetweenAS3.tween(this, { alpha: 0.0 }, null, 1, Sine.easeInOut);
		blink   = BetweenAS3.serial(
			BetweenAS3.tween(this, { alpha: 0.6 }, null, 1, Sine.easeInOut),
			BetweenAS3.tween(this, { alpha: 1.0 }, null, 1, Sine.easeInOut)
		);
		
		fadeIn.onComplete = blink.play;
	}
	
	
	public function appear():void
	{
		blink.stopOnComplete = false;
		blink.onComplete     = null;
		fadeIn.play();
	}
	
	
	public function disappear():void
	{
		blink.stopOnComplete = true;
		blink.onComplete     = fadeOut.play;
	}
}

Code Fullscreen

Preview Fullscreen