astatic notes

package
{
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.utils.getTimer;
 
	/**
	 * Simple test for sorting algorithms
	 * @author Eugene Zatepyakin
	 */
	public class SortTest extends Sprite
	{
 
		private var centzs:Vector.<Number>;
		private var ord:Vector.<int>;
 
		private var arr:Array;
 
		public function SortTest()
		{
			if (stage) {
				init();
			} else {
				addEventListener(Event.ADDED_TO_STAGE, init);
			}
		}
 
		private function init(e:Event = null):void
		{
			removeEventListener(Event.ADDED_TO_STAGE, init);
 
			var t:int = 100;
 
			centzs = new Vector.<Number>();
			ord = new Vector.<int>();
			arr = new Array();
 
			for (var i:int = 0; i < t; i++)
			{
				centzs[i] = 1000 - Math.random() * 2000;
				ord[i] = i;
				arr[i] = centzs[i];
			}
 
			var tt:int = getTimer();
 
			// Quick Sort + Insertion Sort
			//qsort(0, int(t - 1));
			//InsertionSort(0, int(t - 1));
 
			// 3 Way Quick Sort
			//qsort3(0, int(t - 1));
 
			// Quick Sort + Bubble Sort
			//qsort2(0, int(t - 1));
 
			// Built in Array sort
			//arr.sort(Array.NUMERIC);
			//arr = arr.sort(Array.NUMERIC | Array.RETURNINDEXEDARRAY);
 
			// qsort + ins // 65 - 84
			// qsort 3way // 74 - 91
			// array // 87 - 103
			// qsort + bubble // 117 - 124
 
 
			trace(getTimer() - tt);
		}
 
		private function InsertionSort(min:int, max:int):void
		{
			var i:int, j:int, k:int, vi:int, v:Number;
			for ( i = int(min + 1); i <= max; i++) {
				v = centzs[ (vi = ord[i]) ];
				j = i;
				while ( (j > min) && (centzs[ ord[ (k = int(j - 1)) ] ] > v) ) {
					ord[j] = ord[k];
					j--;
				}
				ord[j] = vi;
			}
		}
 
		private function qsort(l:int, r:int):void
		{
			const M:int = 4;
			var i:int, j:int, k:int, vi:int, v:Number;
			//var loop:int = 0;
 
			if (int(r - l) > M) {
				i = int(r + l) >> 1;
				if (centzs[ ord[l] ] > centzs[ ord[i] ]) {
					//swap(l, i);
					vi = ord[l];
					ord[l] = ord[i];
					ord[i] = vi;
				}
				if (centzs[ ord[l] ] > centzs[ ord[r] ]) {
					//swap(l, r);
					vi = ord[l];
					ord[l] = ord[r];
					ord[r] = vi;
				}
				if (centzs[ ord[l] ] > centzs[ ord[r] ]) {
					//swap(i, r);
					vi = ord[i];
					ord[i] = ord[r];
					ord[r] = vi;
				}
 
				j = int(r - 1);
 
				//swap(i, j);
				vi = ord[i];
				ord[i] = ord[j];
				ord[j] = vi;
 
				i = l;
				v = centzs[ ord[j] ];
 
				while (true) {
					while (centzs[ ord[++i] ] < v);
					while (centzs[ ord[--j] ] > v);
					if (j < i) break;
					//swap(i, j);
					vi = ord[i];
					ord[i] = ord[j];
					ord[j] = vi;
					//if (++loop > 100) { return; }
				}
				//swap(i, r - 1);
				vi = ord[i];
				ord[i] = ord[ (k = int(r - 1)) ];
				ord[k] = vi;
 
				qsort(l, j);
				qsort(int(i + 1), r);
			}
		}
 
		private function qsort3(l:int, r:int):void
		{
			var i:int = int(l - 1), j:int = r, p:int = int(l - 1), q:int = r, vi:int;
 
			if (r <= l) return;
 
			var v:Number = centzs[ ord[r] ];
 
			while (true)
			{
				while (centzs[ ord[++i] ] < v);
				while (v < centzs[ ord[--j] ]) {
					if (j == l) break;
				}
 
				if (i >= j) break;
 
				vi = ord[i];
				ord[i] = ord[j];
				ord[j] = vi;
 
				if (centzs[ ord[i] ] == v) {
					p++;
					vi = ord[p];
					ord[p] = ord[i];
					ord[i] = vi;
				}
				if (v == centzs[ ord[j] ]) {
					q--;
					vi = ord[j];
					ord[j] = ord[q];
					ord[q] = vi;
				}
			}
 
			vi = ord[i];
			ord[i] = ord[r];
			ord[r] = vi;
 
			j = int(i - 1);
			i = int(i + 1);
 
			for (var k:int = l; k < p; k++, j--) {
				vi = ord[k];
				ord[k] = ord[j];
				ord[j] = vi;
			}
			for (k = int(r - 1); k > q; k--, i++) {
				vi = ord[i];
				ord[i] = ord[k];
				ord[k] = vi;
			}
 
			qsort3(l, j);
			qsort3(i, r);
		}
 
		private function qsort2(lo0:int, hi0:int):void
		{
			var lo:int = lo0;
			var hi:int = hi0;
 
			if ((hi-lo) <= 6) {
				bsort(lo, hi);
				return;
			}
 
			var t:int;
			var mid:int = int(lo + hi) >> 1;
			var vi:int = ord[ mid ];
 
			var pivot:int = centzs[ vi ];
			ord[mid] = ord[hi];
			ord[hi] = vi;
 
			while( lo < hi ) {
				/*
				 *  Search forward from a[lo] until an element is found that
				 *  is greater than the pivot or lo >= hi
				 */
				while (centzs[ ord[lo] ] <= pivot && lo < hi) lo++;
				/*
				 *  Search backward from a[hi] until element is found that
				 *  is less than the pivot, or hi <= lo
				 */
				while (pivot <= centzs[ ord[hi] ] && lo < hi ) hi--;
				/*
				 *  Swap elements a[lo] and a[hi]
				 */
				if( lo < hi ) {
					t = ord[lo];
					ord[lo] = ord[hi];
					ord[hi] = t;
				}
			}
			/*
			 *  Put the median in the "center" of the list
			 */
			ord[hi0] = ord[hi];
			ord[hi] = vi;
			/*
			 *  Recursive calls, elements a[lo0] to a[lo-1] are less than or
			 *  equal to pivot, elements a[hi+1] to a[hi0] are greater than
			 *  pivot.
			 */
			qsort2(lo0,int(lo-1));
			qsort2(int(hi+1), hi0);
		}
 
		private function bsort(lo:int, hi:int):void
		{
			var t:int;
			var k:int;
			var flipped:Boolean;
 
			for (var j:int = hi; j > lo; j--) {
				flipped = false;
				for (var i:int = lo; i < j; i++) {
					if ( centzs[ ord[i] ] > centzs[ ord[ (k = int(i+1)) ] ] ) {
						t = ord[i];
						ord[i] = ord[ k ];
						ord[k] = t;
						flipped = true;
					}
				}
				if(!flipped) return;
			}
		}
 
	}
 
}