forked from: 各種ソートアルゴリズムを可視化
元祖 つhttp://0xcc.net/blog/archives/000160.html
// forked from rsakane's 各種ソートアルゴリズムを可視化
/*
元祖 つhttp://0xcc.net/blog/archives/000160.html
*/
package
{
import flash.display.Sprite;
import flash.events.*;
import flash.utils.Timer;
import flash.text.TextField;
import flash.text.TextFormat;
import flash.text.TextFieldAutoSize;
[SWF(backgroundColor="#000000", frameRate=20)]
public class Sort extends Sprite
{
private const STAGESIZE = 300;
private const SIZE:int = 50;
private const SORTSPEED:int = 70;
private var data:Array;
private var timer:Timer;
private var tf:TextField;
private var k:int, l:int; //あんまり使いたくない
public function Sort()
{
tf = new TextField();
tf.y = stage.stageHeight - 50;
tf.autoSize = TextFieldAutoSize.LEFT;
var format:TextFormat = new TextFormat();
format.font = "_typewriter";
format.color = "0xCCCCCC";
format.size = 23;
tf.defaultTextFormat = format;
addChild(tf);
data = new Array(SIZE);
for (var i:int = 0; i < SIZE; i++)
{
var d:Data = new Data(STAGESIZE / SIZE);
d.x = i * STAGESIZE / SIZE;
d.y = i * STAGESIZE / SIZE;
addChild(d);
data[i] = d;
}
bubbleSort();
}
private function random(data:Array):void
{
for (var i:int = 0; i < 100; i++)
{
var a:int = Math.floor(Math.random() * data.length);
var b:int = Math.floor(Math.random() * data.length);
var temp:int = data[a].y;
data[a].y = data[b].y;
data[b].y = temp;
}
}
private function bubbleSort(event:TimerEvent = null):void
{
tf.text = "BubbleSort";
random(data);
timer = new Timer(SORTSPEED);
timer.repeatCount = data.length - 1;
timer.addEventListener(TimerEvent.TIMER, _bubbleSort);
timer.addEventListener(TimerEvent.TIMER_COMPLETE, selectionSort);
timer.start();
}
private function _bubbleSort(event:TimerEvent):void
{
for (var j:int = 0; j < data.length - event.target.currentCount; j++)
{
if (data[j].y > data[j + 1].y) swap(data[j], data[j + 1]);
}
}
private function selectionSort(event:TimerEvent = null):void
{
tf.text = "SelectionSort";
random(data);
timer = new Timer(SORTSPEED);
timer.repeatCount = data.length - 1;
timer.addEventListener(TimerEvent.TIMER, _selectionSort);
timer.addEventListener(TimerEvent.TIMER_COMPLETE, insertionSort);
timer.start();
}
private function _selectionSort(event:TimerEvent):void
{
var i:int = event.target.currentCount - 1;
var min:int = i;
for (var j:int = i + 1; j < data.length; j++)
{
if (data[min].y > data[j].y) min = j;
}
swap(data[min], data[i]);
}
private function swap(a:Data, b:Data)
{
var temp:int = a.y;
a.y = b.y;
b.y = temp;
}
private function insertionSort(event:TimerEvent = null):void
{
tf.text = "InsertionSort";
random(data);
timer= new Timer(SORTSPEED);
timer.repeatCount = data.length - 1;
timer.addEventListener(TimerEvent.TIMER, _insertionSort);
timer.addEventListener(TimerEvent.TIMER_COMPLETE, shellSort);
timer.start();
}
private function _insertionSort(event:TimerEvent):void
{
var i:int = event.target.currentCount;
var tmp:int = data[i].y;
for (var j:int = i; j > 0 && data[j - 1].y > tmp; j--)
{
data[j].y = data[j - 1].y;
}
data[j].y = tmp;
}
private function shellSort(event:TimerEvent = null):void
{
k = data.length / 2;
l = k;
tf.text = "ShellSort";
random(data);
timer = new Timer(SORTSPEED / 2);
timer.repeatCount = 999; //適当
timer.addEventListener(TimerEvent.TIMER, _shellSort);
timer.start();
}
private function _shellSort(event:TimerEvent):void
{
if (l >= data.length)
{
k /= 2;
l = k;
if (k <= 0)
{
timer.stop();
shakerSort();
return;
}
}
var j:int;
var temp:int = data[l].y;
for (j = l - k; j >= 0 && data[j].y > temp; j -= k)
{
data[j + k].y = data[j].y;
}
data[j + k].y = temp;
l++;
}
private function shakerSort(event:TimerEvent = null):void
{
tf.text = "ShakerSort";
random(data);
timer = new Timer(SORTSPEED);
timer.repeatCount = data.length - 1;
timer.addEventListener(TimerEvent.TIMER, _shakerSort);
timer.addEventListener(TimerEvent.TIMER_COMPLETE, heapSort);
timer.start();
}
private function _shakerSort(event:Event):void
{
var i:int = event.target.currentCount;
for (var j:int = 0; j < data.length - i; j++)
{
if (data[j].y > data[j + 1].y) swap(data[j], data[j + 1]);
}
for (j = data.length - i; j > 0; j--)
{
if (data[j].y < data[j - 1].y) swap(data[j], data[j - 1]);
}
}
private function heapSort(event:TimerEvent):void
{
tf.text = "HeapSort";
random(data);
timer = new Timer(SORTSPEED);
timer.repeatCount = (data.length - 2) / 2 + 1;
timer.addEventListener(TimerEvent.TIMER, _heapSort);
timer.addEventListener(TimerEvent.TIMER_COMPLETE, _heapSort2);
timer.start();
}
private function _heapSort(event:TimerEvent = null):void
{
var i:int = event.target.currentCount;
_makeHeap((data.length - 2) / 2 - i + 1, data.length - 1);
}
private function _heapSort2(event:TimerEvent):void
{
timer = new Timer(SORTSPEED);
timer.repeatCount = data.length - 1;
timer.addEventListener(TimerEvent.TIMER, __heapSort2);
timer.addEventListener(TimerEvent.TIMER_COMPLETE, gnomeSort);
timer.start();
}
private function __heapSort2(event:TimerEvent):void
{
var i:int = event.target.currentCount;
swap(data[0], data[data.length - i]);
_makeHeap(0, data.length - i - 1);
}
private function _makeHeap(parent:int, r:int)
{
var p:int = data[parent].y;
while (true)
{
var left:int = parent * 2 + 1;
if (left > r) break;
if (left != r)
{
if (data[left + 1].y > data[left].y) left++;
}
if (p >= data[left].y) break;
data[parent].y = data[left].y;
parent = left;
}
data[parent].y = p;
}
private function gnomeSort(event:TimerEvent = null):void
{
tf.text = "GnomeSort";
random(data);
k = 1, l = 2;
timer = new Timer(SORTSPEED / 3);
timer.repeatCount = 999; //適当
timer.addEventListener(TimerEvent.TIMER, _gnomeSort);
timer.start();
}
private function _gnomeSort(event:TimerEvent):void
{
if (k >= data.length)
{
timer.stop();
end();
return;
}
if (data[k - 1].y <= data[k].y)
{
k = l;
l++;
}
else
{
swap(data[k - 1], data[k]);
k--;
if (k == 0) k = 1;
}
}
private function end(event:TimerEvent = null):void
{
tf.text = "終わり";
}
}
}
import flash.display.Sprite;
class Data extends Sprite
{
public function Data(size:int)
{
graphics.beginFill(0xFF33FF);
graphics.drawRect(0, 0, size, size);
graphics.endFill();
}
}