Let’s see how well our FlashSort and RadixSort functions are performing under specific conditions:
* when the keys in the array are uniques :
ex:[9 7 8 1 3 2 5 6 4 7 8]
* when the array is already sorted
ex:[ 1 2 3 4 5 6 7 8 9]
* when the array is sorted, but backward
ex:[9 8 7 6 5 4 3 2 1]
* when we have lots of duplicate keys
ex:[9 7 8 1 3 9 2 7 9 1 8 2 3 9 ] (ex 9 is there 4x times)
* when we have only 1 key (and nothing to sort)
[1 1 1 1 1 1 1 1 1 1 1 1]
Here my results (when sorting 200K integers):
Interesting to note:
* Radix time is very stable, no matter what is in the arrays. This is expected given the nature of the sorting algorithm.
* Flash sort time is pretty stable too, from 11ms to 18ms in my tests, excluding the special 1 key test, where we have an early exit.
* FlashSort beats Radix when all the elements to sort are identical, only 1 key.
* The worst case scenario for all those sorting algorithms is when there is no duplicate keys, except for Radix, where it doesn’t matter.
* Array native sort goes from 11 to 104 depending on what we have in the array, not very stable sorting time !
What do you get?
Test Code
here the code used for this post, you can find the radix and flashsort code in
those posts:radix flashSort.
public static const sortTest_randomNoDuplicateKeys:int = 0; public static const sortTest_sorted:int = 1; public static const sortTest_invsorted:int = 2; public static const sortTest_duplicateKeys:int = 3; public static const sortTest_uniqeKey:int = 4; public static const sortTest_last:int = 5; private function sortIntegerTestAllBehaviors(n:int):void { for(var i:int=sortTest_randomNoDuplicateKeys;i<sortTest_last;i++) sortIntegerTest(n,i,false); //disable vectorSort, too slow } private function sortIntegerTestNum( nbr:int , sortBehavior:int = -1 , doVectorSort:Boolean=false):void { //generate nbr numbers: var i:int = -1; var array:Vector.<int> = new Vector.<int>(nbr); var array2:Vector.<int> = new Vector.<int>(nbr); var array3:Array = new Array(nbr); var array4:Vector.<int> = new Vector.<int>(nbr); var array5:Vector.<int> = new Vector.<int>(nbr); var array6:Vector.<int> = new Vector.<int>(nbr); var array7:Vector.<int> = new Vector.<int>(nbr); //var array8:Vector.<int> = new Vector.<int>(nbr); var sorted:Vector.<int> = new Vector.<int>(nbr); var half:int = nbr>>1; var duplicateKeys:Number = 1; //100 duplicates if(sortBehavior == sortTest_duplicateKeys) duplicateKeys = 0.01; //all keys 100 times if(sortBehavior == sortTest_uniqeKey) duplicateKeys = 0;//only 1 key for the entire array for(i=-1;(++i)<nbr;) { sorted[i] = (i-half) *duplicateKeys; } if(sortBehavior == sortTest_sorted) { for(i=-1;(++i)<nbr;) { index = i; /*array8[i] = */ array7[i] = array6[i] = array5[i] = array4[i] = array3[i] = array2[i] = array[i] = sorted[index]; } } else if(sortBehavior == sortTest_invsorted) { for(i=-1;(++i)<nbr;) { index = nbr-1-i; /*array8[i] = */ array7[i] = array6[i] = array5[i] = array4[i] = array3[i] = array2[i] = array[i] = sorted[index]; } } else { for(i=-1;(++i)<nbr;) { var index:int = Math.random()*sorted.length; /*array8[i] = */ array7[i] = array6[i] = array5[i] = array4[i] = array3[i] = array2[i] = array[i] = sorted[index]; sorted.splice(index,1); } } sorted.length = nbr; //reset length - our temporary buffer for radix var time1:uint = getTimer(); //RADIX { SortAlgorithms.RadixSort11(array,sorted); } var time2:uint = getTimer(); if(doVectorSort) array2.sort(sortFunc); var time3:uint = getTimer(); //Array { //some code commented to time the copy back and forth from Vector to Array to Vector var ary:Array = array3; //var ary:Array = new Array(array3.length); //for(var yy:int =-1,max:int=array3.length;(++yy-max)>>>31;) // ary[yy]=array3[yy]; ary.sort( Array.NUMERIC); //array3 = Vector.<int>(ary); } var time4:uint = getTimer(); //Shell sort { SortAlgorithms.shellSort(array4); } var time5:uint = getTimer(); //QuickSort { SortAlgorithms.NonRecursiveQuickSortInt(array5); } var time6:uint = getTimer(); //Flashsort { SortAlgorithms.flashSortInt3(array6); } var time7:uint = getTimer(); //Radix Alchemy { SortAlgorithms.RadixSorAlchemyt11(array7); } var time8:uint = getTimer(); //verify sorting in our sorted array /* verifySort(sorted); verifySort(array2); verifySort(array3); verifySort(array4); verifySort(array5); verifySort(array6); verifySort(array7); */ var str:String = "sortInt_k="+nbr; switch(sortBehavior) { case sortTest_randomNoDuplicateKeys:str+="_uniqueKeys";break; case sortTest_sorted:str+="_preSorted";break; case sortTest_invsorted:str+="_preInvSorted";break; case sortTest_duplicateKeys:str+="_dupKeys";break; case sortTest_uniqeKey:str+="_1key";break; } if(doVectorSort) setTest(str, "Vector.sort:" , time3-time2 ); setTest( str , "Shell.sort" , time5-time4 ); setTest( str , "Array.sort" , time4-time3 ); setTest( str ,"Quick.sort" , time6-time5 ); setTest( str ,"Flash.sort" , time7-time6 ); setTest( str ,"Radix.sort" , time2-time1 ); setTest( str , "RadixAlchemy.sort" , time8-time7 ); }
Leave a Reply