package
{
	import flash.display.Sprite;
	import flash.utils.getTimer;

	/**
	 * Vector sorting methods test
	 *
	 * @author Eugene Zatepyakin
	 * @see http://blog.inspirit.ru
	 */
	public class Main extends Sprite
	{

		public function Main()
		{
			test();
		}

		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, 0, int(t - 1));

			trace('qsort+insert:', getTimer() - tt);
			//checkSort(arr1);

			// 3 Way Quick Sort
			arr1 = arr.concat();
			tt = getTimer();

			qsort3Way(arr1, 0, int(t - 1));

			trace('3way qsort:', getTimer() - tt);
			//checkSort(arr1);

			// Non Recursive Quick Sort
			arr1 = arr.concat();
			tt = getTimer();

			nonRecursiveQuickSort(arr1, 0, int(t - 1));

			trace('non recursive qsort:', getTimer() - tt);
			//checkSort(arr1);

			// Optimized Non recursive qsort
			arr1 = arr.concat();
			tt = getTimer();

			OptNonRecursiveQuickSort(arr1, 0, (t - 1));

			trace('opt non recursive qsort:', getTimer() - tt);
			//checkSort(arr1);

			// Non Recursive qsort 2
			arr1 = arr.concat();
			tt = getTimer();

			nonRecursiveQsort2(arr1, t);

			trace('non recursive qsort2:', getTimer() - tt);
			//checkSort(arr1);
			
			// Flash Sort
			arr1 = arr.concat();
			tt = getTimer();

			flashSort(arr1, t);

			res += '\nFlash Sort\t\t\t\t\t' + (getTimer() - tt).toString();
			//checkSort(arr1);

			// Built in Array sort
			tt = getTimer();
			arr2.sort(Array.NUMERIC);

			trace('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])
    			{
					trace("bad sort");
					return;
				}
			}
			trace('sort ok');
		}

	}
}