sort
forked from forked from: FlashSortとやら (diff: 404)
Vector sorting methods test @author Eugene Zatepyakin @see http://blog.inspirit.ru
ActionScript3 source code
/**
* Copyright h_kamizono ( http://wonderfl.net/user/h_kamizono )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/llb4
*/
// forked from h_kamizono's forked from: FlashSortとやら
package
{
import flash.display.Sprite;
import flash.utils.getTimer;
import flash.text.TextField;
/**
* Vector sorting methods test
*
* @author Eugene Zatepyakin
* @see http://blog.inspirit.ru
*/
public class Main extends Sprite
{
private var _tf : TextField;
public function Main()
{
_tf = new TextField();
addChild(_tf);
_tf.width = 465;
_tf.height = 465;
test();
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
}
private function test():void
{
var t:int = 10000;
var arr:Vector.<Number> = new Vector.<Number>(t, true);
var arr2:Array = [];
var arr1:Vector.<Number>;
for (var i:int = 0; i < t; i++)
{
var nn:Number = 1000 - Math.random() * 2000;
arr[i] = nn;
arr2[i] = nn; // this one is for built in array.sort
}
var tt:int;
// Insertion Sort
arr1 = arr.concat();
tt = getTimer();
InsertionSort(arr1, t);
tr('insert:', getTimer() - tt);
checkSort(arr1);
// Insertion Sort by wiki
arr1 = arr.concat();
tt = getTimer();
InsertionSort2(arr1, t);
tr('insert2:', getTimer() - tt);
checkSort(arr1);
// shellsort
arr1 = arr.concat();
tt = getTimer();
shellSort(arr1, t);
tr('shellsort:', getTimer() - tt);
checkSort(arr1);
// flashsort
arr1 = arr.concat();
tt = getTimer();
flashSort(arr1, t);
tr('flashSort:', getTimer() - tt);
checkSort(arr1);
// flashsort + shellsort
arr1 = arr.concat();
tt = getTimer();
flashShellSort(arr1, t);
tr('flashShellSort:', getTimer() - tt);
checkSort(arr1);
// minmax
arr1 = arr.concat();
tt = getTimer();
minmaxSort(arr1, t);
tr('minmaxSort:', getTimer() - tt);
checkSort(arr1);
// patienceSort
arr1 = arr.concat();
tt = getTimer();
patienceSort(arr1, t);
tr('patienceSort:', getTimer() - tt);
checkSort(arr1);
}
public function InsertionSort(arr:Vector.<Number>, n:int):void
{
var i:int, j:int, v:Number;
for(j = 1; j < n; ++j)
{
v = arr[j];
i = int(j - 1);
while(i >= 0 && arr[i] > v)
arr[int(i+1)] = arr[ int(i--) ];
arr[int(i+1)] = v;
}
}
public function InsertionSort2(arr:Vector.<Number>, n:int):void
{
var i:int, j:int, v:Number;
for(i = 1; i < n; ++i)
{
v = arr[i];
if (arr[i - 1] > v)
{
j = i;
do {
arr[j] = arr[j-1];
--j;
} while(j > 0 && arr[j-1] > v);
arr[j] = v;
}
}
}
// http://wonderfl.net/c/ihy9
private function shellSort(data: Vector.<Number>, n:int): void
{
var inc:uint = uint(n/2), i:uint, j:uint, v:Number;
while(inc) {
for(i=inc; i<n; i++) {
v = data[i]; j = i;
while(j >= inc && data[uint(j - inc)] > v) {
data[j] = data[uint(j - inc)];
j = uint(j - inc);
}
data[j] = v;
}
inc = uint(inc / 2.2);
}
}
public function flashSort(a:Vector.<Number>, n:int):void
{
var i:int = 0, j:int = 0, k:int = 0, t:int;
var m:int = n / 20;
if (m < 30) m = 30;
var l:Vector.<int> = new Vector.<int>(m);
var anmin:Number = a[0];
var nmax:int = 0;
var nmove:int = 0;
for (i = 1; i < n; ++i)
{
if (a[i] < anmin) anmin = a[i];
if (a[i] > a[nmax]) nmax = i;
}
if (anmin == a[nmax]) return;
var c1:Number = (m - 1) / (a[nmax] - anmin);
for (i = 0; i < n; ++i)
{
k = int(c1*(a[i] - anmin));
++l[k];
}
for (k = 1; k < m; ++k)
{
l[k] += l[int(k-1)];
}
var hold:Number = a[nmax];
a[nmax] = a[0];
a[0] = hold;
var flash:Number;
j = 0;
k = int(m - 1);
i = int(n - 1);
while (nmove < i)
{
while (j > (l[k]-1))
{
k = int(c1 * (a[ int(++j) ] - anmin));
}
flash = a[j];
while (!(j == l[k]))
{
k = int(c1 * (flash - anmin));
hold = a[ (t = int(l[k]-1)) ];
a[ t ] = flash;
flash = hold;
--l[k];
++nmove;
}
}
for(j = 1; j < n; ++j)
{
hold = a[j];
i = int(j - 1);
while(i >= 0 && a[i] > hold)
a[int(i+1)] = a[ int(i--) ];
a[int(i+1)] = hold;
}
}
public function flashShellSort(a:Vector.<Number>, n:int):void
{
var i:int = 0, j:int = 0, k:int = 0, t:int;
var m:int = n / 20;
if (m < 30) m = 30;
var l:Vector.<int> = new Vector.<int>(m);
var anmin:Number = a[0];
var nmax:int = 0;
var nmove:int = 0;
for (i = 1; i < n; ++i)
{
if (a[i] < anmin) anmin = a[i];
if (a[i] > a[nmax]) nmax = i;
}
if (anmin == a[nmax]) return;
var c1:Number = (m - 1) / (a[nmax] - anmin);
for (i = 0; i < n; ++i)
{
k = int(c1*(a[i] - anmin));
++l[k];
}
for (k = 1; k < m; ++k)
{
l[k] += l[int(k-1)];
}
var hold:Number = a[nmax];
a[nmax] = a[0];
a[0] = hold;
var flash:Number;
j = 0;
k = int(m - 1);
i = int(n - 1);
while (nmove < i)
{
while (j > (l[k]-1))
{
k = int(c1 * (a[ int(++j) ] - anmin));
}
flash = a[j];
while (!(j == l[k]))
{
k = int(c1 * (flash - anmin));
hold = a[ (t = int(l[k]-1)) ];
a[ t ] = flash;
flash = hold;
--l[k];
++nmove;
}
}
var inc:uint = uint(n/2), v:Number;
while(inc) {
for(i=inc; i<n; i++) {
v = a[i]; j = i;
while(j >= inc && a[uint(j - inc)] > v) {
a[j] = a[uint(j - inc)];
j = uint(j - inc);
}
a[j] = v;
}
inc = uint(inc / 2.2);
}
}
public function minmaxSort(v:Vector.<Number>, n:int):void
{
var i:int =0, j:int = n -1, ma:Number, mai:uint, mi:Number, mii:uint, k:uint, tmp:Number;
while (i < j)
{
ma = v[j]; mai = j; mi = v[i]; mii = i;
for (k = i; k <= j; ++k)
{
if (ma < v[k])
{
ma = v[k]; mai = k;
}
if (mi > v[k])
{
mi = v[k]; mii = k;
}
}
if (mii == j && mai == i)
{
tmp = v[j]; v[j] = v[i]; v[i] = tmp;i++;j--; continue;
}
if (i == mai)
{
tmp = v[mii]; v[mii] = v[i]; v[i] = tmp;
tmp = v[mii]; v[mii] = v[j]; v[j] = tmp; i++;j--; continue;
}
tmp = v[mii]; v[mii] = v[i]; v[i] = tmp;
tmp = v[mai]; v[mai] = v[j]; v[j] = tmp;
i++;j--;
}
}
// http://home.westman.wave.ca/~rhenry/sort/src/PatienceSortAlgorithm.java
public function patienceSort(v:Vector.<Number>, n:int):void
{
var piles:Vector.<Vector.<Number>> = new Vector.<Vector.<Number>>;
var first:Vector.<Number> = new Vector.<Number>;
first.push(v[0]);
piles.push(first);
//sort into piles
for (var a:uint = 1; a < n; a++)
{
var notFound:Boolean = true;
for (var i:uint = 0; i < piles.length && notFound; i++)
{
var pile:Vector.<Number> = piles[i];
var top:Number = pile[pile.length-1];
if (top >= v[a])
{
pile.push(v[a]);
notFound = false;
}
}
if (notFound)
{
var newPile:Vector.<Number> = new Vector.<Number>;
newPile.push (v[a]);
piles.push(newPile);
}
}
var c:int = 0;
while (c < n)
{
var small:int = 0;
//find minimum value of top cards
for (a = 1; a < piles.length; a++)
{
var pile1:Vector.<Number> = piles[a];
var pile2:Vector.<Number> =piles[small];
var n1:Number = pile1[pile1.length-1];
var n2:Number = pile2[pile2.length-1];;
if (n1 < n2)
{
small = a;
}
}
var smallPile:Vector.<Number> = piles[small];
v[c] = smallPile[smallPile.length-1];
smallPile.pop();
if (piles[small].length ==0)
{
piles.splice(small,1);
//piles.remove (small);
}
c++;
}
}
public function checkSort(arr:Vector.<Number>):void
{
var n:int = arr.length;
for (var i:int = 1; i < n; ++i)
{
if (arr[int(i - 1)] > arr[i])
{
tr("bad sort");
return;
}
}
tr('sort ok');
}
}
}