FlashSortとやら
Vector sorting methods test
@author Eugene Zatepyakin
@see http://blog.inspirit.ru
/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/qOca
*/
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 = 100000;
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;
// Quick Sort + Insertion Sort
// I guess this one could be faster
// if we only could merge two functions in to one
arr1 = arr.concat();
tt = getTimer();
qsort(arr1, 0, int(t - 1));
InsertionSort(arr1, int(t - 1));
tr('qsort+insert:', getTimer() - tt);
//checkSort(arr1);
// 3 Way Quick Sort
arr1 = arr.concat();
tt = getTimer();
qsort3Way(arr1, 0, int(t - 1));
tr('3way qsort:', getTimer() - tt);
//checkSort(arr1);
// Non Recursive Quick Sort
arr1 = arr.concat();
tt = getTimer();
nonRecursiveQuickSort(arr1, 0, int(t - 1));
tr('non recursive qsort:', getTimer() - tt);
//checkSort(arr1);
// Optimized Non recursive qsort
arr1 = arr.concat();
tt = getTimer();
OptNonRecursiveQuickSort(arr1, 0, (t - 1));
tr('opt non recursive qsort:', getTimer() - tt);
//checkSort(arr1);
// Non Recursive qsort 2
arr1 = arr.concat();
tt = getTimer();
nonRecursiveQsort2(arr1, t);
tr('non recursive qsort2:', getTimer() - tt);
//checkSort(arr1);
// Flash Sort
arr1 = arr.concat();
tt = getTimer();
flashSort(arr1, t);
tr('Flash Sort\t\t\t\t\t', (getTimer() - tt));
//checkSort(arr1);
// Built in Array sort
tt = getTimer();
arr2.sort(Array.NUMERIC);
tr('array.sort:', getTimer() - tt);
}
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 qsort(arr:Vector.<Number>, l:int, r:int):void
{
var i:int, j:int, k:int, vi:int, v:Number;
if ((r - l) > 10)
{
i = int(r + l) >> 1;
if ( arr[l] > arr[i] )
{
vi = arr[l];
arr[l] = arr[i];
arr[i] = vi;
}
if ( arr[l] > arr[r] )
{
vi = arr[l];
arr[l] = arr[r];
arr[r] = vi;
}
if ( arr[l] > arr[r] )
{
vi = arr[i];
arr[i] = arr[r];
arr[r] = vi;
}
j = int(r - 1);
vi = arr[i];
arr[i] = arr[j];
arr[j] = vi;
i = l;
v = arr[j];
while (true)
{
while ( arr[ int( ++i ) ] < v);
while ( arr[ int( --j ) ] > v);
if (j < i) break;
vi = arr[i];
arr[i] = arr[j];
arr[j] = vi;
}
vi = arr[i];
arr[i] = arr[ (k = int(r - 1)) ];
arr[k] = vi;
qsort(arr, l, j);
qsort(arr, int(++i), r);
}
}
private function qsort3Way(arr:Vector.<Number>, l:int, r:int):void
{
if((r - l) <= 10) return;
var i:int = int(l - 1), j:int = r, p:int = int(l - 1), q:int = r, vi:Number;
//if (r <= l) return;
var v:Number = arr[r];
while (true)
{
while ( arr[ int( ++i ) ] < v);
while (v < arr[ int( --j ) ] ) {
if (j == l) break;
}
if (i >= j) break;
vi = arr[i];
arr[i] = arr[j];
arr[j] = vi;
if (arr[i] == v)
{
vi = arr[ int( ++p ) ];
arr[p] = arr[i];
arr[i] = vi;
}
if (v == arr[j])
{
vi = arr[j];
arr[j] = arr[ int( --q ) ];
arr[q] = vi;
}
}
vi = arr[i];
arr[i] = arr[r];
arr[r] = vi;
j = int(i - 1);
i = int(i + 1);
for (var k:int = l; k < p; ++k, --j)
{
vi = arr[k];
arr[k] = arr[j];
arr[j] = vi;
}
for (k = (r - 1); k > q; --k, ++i)
{
vi = arr[i];
arr[i] = arr[k];
arr[k] = vi;
}
qsort3Way(arr, l, j);
qsort3Way(arr, i, r);
}
public function nonRecursiveQuickSort(arr:Vector.<Number>, min:int, max:int):void
{
var Stack:Vector.<int> = new Vector.<int>(128, true); // Stack for array bounds
var top:int = -1;
var n:int = int(max + 1);
var pivot:Number, temp:Number;
var pivotindex:int, l:int, r:int, i:int, j:int;
Stack[ int(++top) ] = min; // Initialize stack
Stack[ int(++top) ] = max;
while (top > 0) // While there are unprocessed subarrays
{
// Pop Stack
j = Stack[ int(top--) ];
i = Stack[ int(top--) ];
// Findpivot
pivotindex = int(i+j) >> 1;
pivot = arr[pivotindex];
// Stick pivot at end
arr[pivotindex] = arr[j];
arr[j] = pivot;
// Partition
l = (i - 1);
r = j;
do
{
while (arr[ int(++l) ] < pivot);
while ((r!=0) && (arr[ int(--r) ] > pivot));
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
} while (l < r);
// Undo final swap
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// Put pivot value in place
temp = arr[l];
arr[l] = arr[j];
arr[j] = temp;
// Put new subarrays onto Stack if they are small
if ((l-i) > 10) // Left partition / 10 could be adjusted from 0 - ...
{
Stack[ int(++top) ] = i;
Stack[ int(++top) ] = (l-1);
}
if ((j-l) > 10) // Right partition / 10 could be adjusted from 0 - ...
{
Stack[ int(++top) ] = (l+1);
Stack[ int(++top) ] = j;
}
}
for(j = 1; j < n; ++j)
{
temp = arr[j];
i = int(j - 1);
while(i >= 0 && arr[i] > temp)
arr[int(i+1)] = arr[ int(i--) ];
arr[int(i+1)] = temp;
}
}
public function OptNonRecursiveQuickSort(c:Vector.<Number>, min:int, max:int):void
{
var i:int, j:int, left:int = min, right:int = max, stack_pointer:int = -1;
var median:int;
var stack:Vector.<int> = new Vector.<int>(128, true);
var swap:Number, temp:Number;
while(true){
if(right - left <= 10) // use insertion sort
{
for(j = int(left+1); j <= right; ++j)
{
swap = c[j];
i = int(j - 1);
while(i >= left && c[i] > swap)
c[int(i+1)] = c[ int(i--) ];
c[int(i+1)] = swap;
}
if(stack_pointer == -1) break;
right = stack[ int(stack_pointer--) ];
left = stack[ int(stack_pointer--) ];
} else {
median = int(left + right) >> 1;
i = (left + 1);
j = right;
swap = c[median]; c[median] = c[i]; c[i] = swap;
if(c[left] > c[right])
{
swap = c[left]; c[left] = c[right]; c[right] = swap;
}
if(c[i] > c[right])
{
swap = c[i]; c[i] = c[right]; c[right] = swap;
}
if(c[left] > c[i])
{
swap = c[left]; c[left] = c[i]; c[i] = swap;
}
temp = c[i];
while(true){
//do i++; while(c[i] < temp);
//do j--; while(c[j] > temp);
while(c[ int(++i) ] < temp);
while(c[ int(--j) ] > temp);
if(j < i) break;
swap = c[i]; c[i] = c[j]; c[j] = swap;
}
c[int(left + 1)] = c[j];
c[j] = temp;
if((right-i+1) >= (j-left))
{
stack[ int(++stack_pointer) ] = i;
stack[ int(++stack_pointer) ] = right;
right = int(--j);
} else {
stack[ int(++stack_pointer) ] = left;
stack[ int(++stack_pointer) ] = int(--j);
left = i;
}
}
}
}
public function nonRecursiveQsort2(arr:Vector.<Number>, els:int):void
{
var piv:Number, i:int = 0, j:int, L:int, R:int;
var beg:Vector.<int> = new Vector.<int>(128, true);
var end:Vector.<int> = new Vector.<int>(128, true);
beg[0] = 0; end[0] = els;
while ( i >= 0 )
{
L = beg[i]; R = end[i] - 1;
if (L < R)
{
piv = arr[L];
while (L < R)
{
while (arr[R] >= piv && L<R) --R; if (L<R) arr[ int(L++) ] = arr[R];
while (arr[L] <= piv && L<R) ++L; if (L<R) arr[ int(R--) ] = arr[L];
}
arr[L] = piv; beg[ (j = int(i+1)) ] = (L+1); end[j] = end[i]; end[ int(i++) ] = L;
}
else {
--i;
}
}
}
public function flashSort(a:Vector.<Number>, n:int):void
{
var i:int = 0, j:int = 0, k:int = 0, t:int;
var m:int = int(n * .125);
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 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');
}
}
}