/**
* Copyright heroboy ( http://wonderfl.net/user/heroboy )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/ghw9
*/
package
{
import flash.display.Graphics;
import flash.display.Sprite;
import flash.display.StageAlign;
import flash.events.Event;
import com.bit101.components.PushButton;
import com.bit101.components.ComboBox;
public class Main extends Sprite
{
private var canvas:Sprite;
private var canvasWidth:int;
private var canvasHeight:int;
private var nums:Array = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
private var sortor:ISortor = new BubbleSort();
public function Main():void
{
if (stage) init();
else addEventListener(Event.ADDED_TO_STAGE, init);
}
private function init(e:Event = null):void
{
removeEventListener(Event.ADDED_TO_STAGE, init);
canvasWidth = stage.stageWidth;
canvasHeight = stage.stageHeight - 20;
stage.align = StageAlign.TOP_LEFT;
canvas = new Sprite();
canvas.y = 20;
addChild(canvas);
var btn:PushButton = new PushButton(this, 0, 0, "shuffle",onShuffle);
var combo:ComboBox = new ComboBox(this, btn.width, 0, "BubbleSort", [
"BubbleSort",
"HeapSort",
"MergeSort",
"QuickSort",
"SelectionSort"]);
combo.addEventListener(Event.SELECT, onSelect);
onShuffle(null);
//update(new BubbleSort(),arr);
}
private function onSelect(e:Event):void
{
var combo:ComboBox = e.target as ComboBox;
var s:String = combo.selectedItem as String;
if (s == "BubbleSort")
sortor = new BubbleSort();
else if (s == "HeapSort")
sortor = new HeapSort();
else if (s == "MergeSort")
sortor = new MergeSort();
else if (s == "QuickSort")
sortor = new QuickSort();
else if (s == "SelectionSort")
sortor = new SelectionSort();
update(sortor, nums);
}
private function onShuffle(e:Event):void
{
var arr:Array = nums;
for (var i:int = 0; i < arr.length * arr.length;++i )
{
var j:int = int(Math.random() * arr.length);
var k:int = int(Math.random() * arr.length);
var tmp:int = arr[j];
arr[j] = arr[k];
arr[k] = tmp;
}
update(sortor, arr);
}
private function update(sortor:ISortor,nums:Array):void
{
var arr:Array = [];
var node:SortNode;
for (var i:int = 0; i < nums.length;++i )
{
node = new SortNode(nums[i]);
var c:uint = 0xff * nums[i] / nums.length;
node.color = (c << 16) | (c << 8) | c;
arr.push(node);
}
sortor.reset(arr, SortNode.Compare);
var arrArr:Array = sortor.result;
for each( node in arr)
{
node.getPositionInArray(arrArr);
}
//draw
var step:int = arrArr.length;
var g:Graphics = canvas.graphics;
var gapx:Number = canvasWidth / step;
var gapy:Number = canvasHeight / arr.length;
g.clear();
var bg1:uint = 0x773333;
var bg2:uint = 0x333377;
for (i = 0; i < step;++i )
{
g.beginFill(i % 2 == 0?bg1:bg2, 1);
g.drawRect(i * gapx, 0, gapx, canvasHeight);
g.endFill();
}
for each(node in arr)
{
var j:int;
var x:Number;
var y:Number;
g.lineStyle(5, node.color);
for (i = 0; i < node.positionIndex.length;++i )
{
j = node.positionIndex[i];
x = i * gapx + gapx / 2;
y = j * gapy + gapy / 2;
if (i == 0) g.moveTo(x, y);
else g.lineTo(x, y);
}
}
}
}
}
class SortNode
{
public var value:int;
public var color:uint;
public var positionIndex:Vector.<int>;
public function SortNode(val:int)
{
value = val;
}
public function getPositionInArray(arrArr:Array):void
{
positionIndex = new Vector.<int>();
for each(var arr:Array in arrArr)
{
positionIndex.push(arr.indexOf(this));
}
}
public static function Compare(a:SortNode, b:SortNode):Number
{
return a.value - b.value;
}
}
interface ISortor
{
function reset(arr:Array, cmp:Function):void;
function get result():Array;
}
class BubbleSort implements ISortor
{
private var _result:Array;
public function BubbleSort()
{
}
public function reset(arr:Array, cmp:Function):void
{
//if (cmp == null) cmp = Util.defaultCmp;
_result = [];
arr = arr.slice();
var nCount:uint = arr.length;
var bSwapped:Boolean = true;
while (bSwapped)
{
_result.push(arr.slice());
bSwapped = false;
var i:uint;
for (i = 0; i < nCount-1;++i )
{
if ( cmp(arr[i], arr[i + 1]) > 0 )
{
bSwapped = true;
var tmp:* = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
}
}
}
}
public function get result():Array
{
return _result;
}
}
class HeapSort implements ISortor
{
private var _result:Array;
public function HeapSort()
{
}
private static function _siftDown(arr:Array,cmp:Function,start:int,end:int):void
{
var root:int = start;
var child:int;
while( root*2+1<end )
{
child = root*2+1;
if (child+1<end && cmp(arr[child],arr[child+1])<0)
child = child+1;
if (cmp(arr[root],arr[child])<0)
{
var tmp:* = arr[root];
arr[root] = arr[child];
arr[child]=tmp;
root = child;
}
else
{
return;
}
}
}
private static function _heapify(arr:Array,cmp:Function):void
{
var start:int = (arr.length-2)/2;
//if (arr.length<2) start=0;
while (start>=0)
{
_siftDown(arr,cmp,start,arr.length);
start = start-1;
}
}
private static function _heapSort(arr:Array,cmp:Function,stepFunc:Function):void
{
stepFunc();
_heapify(arr,cmp);
stepFunc();
var end:int = arr.length-1;
while(end > 0)
{
var tmp:* = arr[end];
arr[end] = arr[0];
arr[0]=tmp;
_siftDown(arr,cmp,0,end);
end = end - 1;
stepFunc();
}
}
public function reset(arr:Array, cmp:Function):void
{
_result = [];
function stepFunc():void
{
_result.push(arr.slice());
}
_heapSort(arr,cmp,stepFunc);
}
public function get result():Array
{
return _result;
}
}
class MergeSort implements ISortor
{
private var _result:Array;
public function MergeSort()
{
}
private function _merge(arr:Array,cmp:Function,low:uint,mid:uint,high:uint,stepFunc:Function):void
{
var left:uint = low;//to mid
var right:uint = mid;//to high
var result:Array = [];
while (left<mid && right<high)
{
if (cmp(arr[left],arr[right])<=0)
{
result.push(arr[left]);
left++;
}
else
{
result.push(arr[right]);
right++;
}
}
var i:uint;
if (left < mid)
{
for(i=left;i<mid;++i)
result.push(arr[i]);
}
else
{
for(i=right;i<high;++i)
result.push(arr[i]);
}
for (i=low;i<high;++i)
arr[i] = result[i-low];
}
private function _mergeSort(arr:Array,cmp:Function,low:uint,high:uint,stepFunc:Function):void
{
if (low >= high || high-low<=1)
{
return;
}
var mid:uint = (low+high)/2;
_mergeSort(arr,cmp,low,mid,stepFunc);
_mergeSort(arr,cmp,mid,high,stepFunc);
stepFunc();
if (mid > low && high>mid)
{
_merge(arr,cmp,low,mid,high,stepFunc);
}
}
public function reset(arr:Array, cmp:Function):void
{
_result = [];
function stepFunc():void
{
_result.push(arr.slice());
}
_mergeSort(arr,cmp,0,arr.length,stepFunc);
_result.push(arr.slice());
}
public function get result():Array
{
return _result;
}
}
class QuickSort implements ISortor
{
private var _result:Array;
public function QuickSort()
{
}
private static function getPivotIndex(arr:Array,cmp:Function):uint
{
return uint(arr.length/2);
}
private static function _unfoldArray(arr:Array):Array
{
var result:Array = [];
function innerUnfold(coll:Array):void
{
for each(var item:* in coll)
{
if (item is Array)
innerUnfold(item as Array);
else
result.push(item);
}
}
innerUnfold(arr);
return result;
}
/*
* arr as Array of element
* return [less as Array, pivot as element, greater as Array];
*/
private static function _quickSort1Step(arr:Array,cmp:Function):Array
{
var pivotIndex:uint = getPivotIndex(arr,cmp);
var pivot:* = arr[pivotIndex];
var less:Array = [];
var greater:Array = [];
var i:uint;
//trace("pivot:"+pivot);
for(i=0;i<arr.length;++i)
{
if (i == pivotIndex) continue;
if (cmp(arr[i],pivot)<=0)
less.push(arr[i]);
else
greater.push(arr[i]);
}
var result:Array = [];
if (less.length == 1)
result.push(less[0]);
else if (less.length > 1)
result.push(less);
result.push(pivot);
if (greater.length == 1)
result.push(greater[0]);
else if (greater.length > 1)
result.push(greater);
return result;
}
private static function _cleanArray(arr:Array):Array
{
var result:Array = [];
var tmp:Array;
for each(var item:* in arr)
{
if (item is Array)
{
tmp = _cleanArray(item as Array);
if (tmp.length == 1)
result.push(tmp[0]);
else if (tmp.length > 1)
result.push(tmp);
}
else
{
result.push(item);
}
}
return result;
}
private static function _quickSort(arr:Array,cmp:Function,low:uint,high:uint,stepFunc:Function):void
{
var tmp:*;
if (low >= high || high-low<1)
{
//stepFunc();
return;
}
var pivotIndex:uint = low;
var pivot:* = arr[pivotIndex];
var newArr:Array = [];
var i:uint = 0;
var newPivotIndex:uint;
for(i=low;i<high;++i)
{
if (i == pivotIndex) continue;
if (cmp(arr[i],pivot)<=0)
newArr.push(arr[i]);
}
newPivotIndex = newArr.length + low;
newArr.push(pivot);
for(i=low;i<high;++i)
{
if (i == pivotIndex) continue;
if (cmp(arr[i],pivot)>0)
newArr.push(arr[i]);
}
for(i=low;i<high;++i)
{
arr[i] = newArr[i-low];
}
stepFunc();
_quickSort(arr,cmp,low,newPivotIndex,stepFunc);
_quickSort(arr,cmp,newPivotIndex+1,high,stepFunc);
}
public function reset(arr:Array, cmp:Function):void
{
_result = [];
arr = arr.slice();
function stepFunc():void
{
_result.push(arr.slice());
}
_quickSort(arr,cmp,0,arr.length,stepFunc);
//_result.push(arr);
}
public function resetX(arr:Array, cmp:Function):void
{
_result = [];
arr = [arr];
var i:uint,j:uint;
var tmparr:Array;
var nextArrays:Array = arr;
var nextNextArrays:Array;
while(nextArrays.length > 0)
{
_result.push(_unfoldArray(arr));
nextNextArrays = [];
for(i=0;i<nextArrays.length;++i)
{
tmparr = nextArrays[i] as Array;
if (tmparr)
{
tmparr = _quickSort1Step(tmparr,cmp);
(nextArrays[i] as Array).length = 0;
for(j=0;j<tmparr.length;++j)
(nextArrays[i] as Array).push(tmparr[j]);
for each(var item:* in nextArrays[i])
{
if (item is Array && (item as Array).length>1)
{
nextNextArrays.push(item);
}
}
}
}
nextArrays = nextNextArrays
}
}
public function get result():Array
{
return _result;
}
}
class SelectionSort implements ISortor
{
private var _result:Array;
public function SelectionSort()
{
}
public function reset(arr:Array, cmp:Function):void
{
_result = [];
var i:uint,j:uint;
var minidx:uint;
var nCount:uint = arr.length;
var tmp:*,t:uint;
arr = arr.slice();
for(i=0;i<nCount;++i)
{
_result.push(arr.slice());
minidx = i;
for(j=minidx+1;j<nCount;++j)
{
if (cmp(arr[j],arr[minidx])<0)
{
t = j;
j = minidx;
minidx = t;
}
}
if (minidx != i)
{
tmp = arr[i];
arr[i]=arr[minidx];
arr[minidx]=tmp;
}
}
}
public function get result():Array
{
return _result;
}
}