SHARE
TWEET

Untitled

tinyevil Nov 28th, 2018 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package com.meduzik.utils
  2. {
  3.     public class VectorSort{
  4.         public static function Sort(v:*, comparator:Function):void
  5.         {
  6.             var n:int = v.length;
  7.             if ( n >= 30 ) {
  8.                 QSort(v, comparator, 0, n);
  9.             }else {
  10.                 InsertionSort(v, comparator, 0, n);
  11.             }
  12.         }
  13.        
  14.         private static function QSort(v:*, comparator:Function, begin:int, end:int):void
  15.         {
  16.         tailcall:
  17.             var x1:* = v[begin];
  18.             var x2:* = v[(begin + end) >> 1];
  19.             var x3:* = v[end - 1];
  20.            
  21.             var c1:Boolean = comparator(x1, x2) < 0;   
  22.             var c3:Boolean = comparator(x2, x3) < 0;
  23.            
  24.             var pivot:*;
  25.            
  26.             if ( c1 == c3 ) {
  27.                 pivot = x2;
  28.             }else{
  29.                 var c2:Boolean = comparator(x1, x3) < 0;
  30.                 if ( c2 != c3 ) {
  31.                     pivot = x3;
  32.                 }else {
  33.                     pivot = x1;
  34.                 }
  35.             }
  36.            
  37.             var low:int = begin;
  38.             var mid:int = begin;
  39.             var high:int = end;
  40.             for ( var i:int = begin; i < high; i++ ) {
  41.                 var cmp:Number = comparator(v[i], pivot);
  42.                 if ( cmp < 0 ) {
  43.                     var tmp:* = v[low];
  44.                     v[low] = v[i];
  45.                     v[i] = tmp;
  46.                    
  47.                     low++;
  48.                 }else if ( cmp > 0 ) {
  49.                     --high;
  50.                     tmp = v[high];
  51.                     v[high] = v[i];
  52.                     v[i] = tmp;
  53.                     i--;
  54.                 }
  55.             }
  56.            
  57.             var first:int = low - begin;
  58.             var second:int = end - high;
  59.            
  60.             if ( first <= 8 ) {
  61.                 InsertionSort(v, comparator, begin, low);
  62.                 if ( second <= 8 ){
  63.                     InsertionSort(v, comparator, high, end);
  64.                 }else {
  65.                     begin = high;
  66.                     goto tailcall;
  67.                 }
  68.             }else if ( second <= 8 ) {
  69.                 InsertionSort(v, comparator, high, end);               
  70.                 end = low;
  71.                 goto tailcall;
  72.             }else {
  73.                 if ( first < second ) {
  74.                     QSort(v, comparator, begin, low);
  75.                     begin = high;
  76.                 }else {
  77.                     QSort(v, comparator, high, end);
  78.                     end = low;
  79.                 }
  80.                 goto tailcall;
  81.             }
  82.         }
  83.  
  84.         [Inline]
  85.         private static function InsertionSort(v:*, comparator:Function, begin:int, end:int):void
  86.         {
  87.             var n:int = end - begin;
  88.             for ( var i:int = 0; i < n; i++ ) {
  89.                 var j:int = i + begin;
  90.                 var x:* = v[j];
  91.                 while ( j > begin && comparator(x, v[j - 1]) < 0 ) {
  92.                     v[j] = v[j - 1];
  93.                     j--;
  94.                 }
  95.                 v[j] = x;
  96.             }
  97.         }
  98.     }
  99. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top