Who is the fastest in sorting data (Array.prototype.sort PK quick sort in javascript)_javascript skills

But what surprised me was that a netizen replied below that the sort method of Array itself in JavaScript is the fastest, faster than the quick sort algorithm. I was very depressed when I saw it because it took so long I have been working on the sorting algorithm for a long time, and I actually forgot about the sort method of Array itself
But is the built-in sort method in javascript really faster than the quick sort algorithm?
Haha, you will know after you test it
Let me first talk about my testing environment
1. My testing environment is IE6.0 and firefox2.0
2. Each algorithm has many differences. Implementation method. In the following test, I chose the quick sort algorithm implemented by the netizen above, and just moved the embedded function outside
3. The execution speed of the algorithm is related to the type, size and amount of data. I Here we only compare the sorting of integers less than 999999, and the data amounts are set to 500, 2000, and 30000 respectively

About the sort method: The sort method is a built-in method of Array: The authoritative guide to javascript is defined like this:

The sort( ) method sorts the elements of array in place: no copy of the array is made. If sort( ) is called with no arguments, the elements of the array are arranged in alphabetical order (more precisely, the order determined by the character encoding). To do this, elements are first converted to strings, if necessary, so that they can be compared.
If you want to sort the array elements in some other order, you must supply a comparison function that compares two values ​​and returns a number indicating their relative order. The comparison function should take two arguments, a and b, and should return one of the following:

The sort method can accept a function type parameter You can customize your own sorting logic. When no parameters are provided, the default is to sort in character order. Therefore, you need to provide a function type parameter to sort integers. The calling method of this test is as follows:

array.sort(function (a,b){return a-b})

Of course, if the number of integers to be sorted is the same, the result returned without providing parameters will be the same. You will know after testing:

Copy code The code is as follows:

<script> <br>alert( [3,4,5,11,1]. sort()) <br>alert([3,4,5,11,1].sort(function(a,b){return a-b})) <br></script>

Prompt : You can modify it first and then run
. The result is [1, 11, 3, 4, 5], which is obviously not the result we want.
generates an array that needs to be sorted. In order to get a fair result, I randomly generate it first. The array used for sorting, the arrays used by both methods have the same elements in each comparison, below is the code to generate the random array

Copy code The code is as follows:

function random(m,n){
//Generate an integer between m and n
var i=Math.random() ;
return Math.round((n-m)*i m);
}

function getRandomArr(m,n,l){
//m: Generate the minimum value of a random integer, n: The maximum value of the generated random integer, l: The length of the generated array
var resultArr=[];
for(var i=0;iresultArr.push(random (m,n))
}
return resultArr;
}

Implementation of quick sort algorithm, this algorithm is taken from the implementation of this netizen on the 51js forum that I saw , the code is as follows:

Copy code The code is as follows:

function doSort(a,s,e )
{
if(s{
var pos=partition(a,s,e);
doSort(a,s,pos-1);
doSort(a,pos 1,e);
}
}
function partition(a,st,en)
{
var s=st;
var e=en 1 ;
var temp=a[s];
while(1)
{
while(a[ s]while(a[--e]> temp);
if(s>e)break;
var tem=a[s];
a[s]=a[e];
a[e]=tem;
}
a[st]=a[e];
a[e]=temp;
return e;
}

Array.prototype.quickSort=function() {
doSort(this,0,this.length-1);
}

Check whether the result is correct using array.join(). The performance test code is as follows:

Copy code The code is as follows:

function sortIntF(a,b){return a-b}
function pk(num){
//num: The number of elements of the array used for sorting
//Generate the Sorted array
var arr=getRandomArr(1,999999,num);
//When the number of elements is less than 10000, execute n times to take the average value
var n=Math.ceil(10000/num );
//Generate multiple copies of the array for sorting
var quickSortArrs=[];
var sortArrs=[];
for(var i=0;iquickSortArrs.push(arr.slice(0));
sortArrs.push(arr.slice(0));
}
var t1=new Date();
for(var i=0;iquickSortArrs[i].quickSort();
}
var t2=new Date();
for(var i=0 ;isortArrs[i].sort(sortIntF);
}
var t3=new Date();
alert("Performance comparison, for " num " For an array of elements, the average time spent per sort is as follows: n"
"Array.prototype.sort:" ((t3-t2)/n) "msn"
"quickSort:" ((t2-t1) /n) "msn"
);
alert("Is the sorting result correct:" (sortArrs[0].join()==quickSortArrs[0].join()));
}

Just call the pk function directly. For example, if you want to compare the sorting performance of an array of 300 elements, just call pk(300)

The complete test code is as follows:

[Ctrl A Select all Note: If you need to introduce external Js, you need to refresh to execute

]

Test results
No. once first time (ms)
500 elements: ie6.0: sort: 38.3 39.05 39.05
quickSort: 8.6 8.6 9.4
ff2.0: sort: 3.1 3.15 3.9
quickSort: 4.7 4.7 3.15

2000 elements: ie6.0: sort: 200 203.2 203
quickSort: 40.6 43.6 43.8
ff2.0: sort: 18.8 18.6 18.8
quickSort: 18.6 15.6 15.6

30000 elements: ie6.0: sort: 10360 9765 9203
quickSort: 843 813 891
ff2.0: sort: 422 422 406
quickSort: 328 297 4 07
As you can see from the results,
In IE6.0, the quick sort algorithm is much faster than the sort method of the Array object. For relatively few elements, the speed of quick sort is basically about 5 times that of the sort method. For 30,000 elements, quick sort is more than ten times faster than the sort method
In ff2.0, the speed of the two sorting algorithms is basically the same, and the quick sort algorithm is slightly faster. This also shows that the sort of Array objects in ff2.0 is still the same. The more efficient one may be to use quick sort, because it is very close to the data of the quick sort algorithm Note: The above test only represents the test results on my local machine. The results may be different on your machine. The difference, I hope everyone can help test it <script> function rand(m,n){ //生成一个m、n之间的整数 var i=Math.random(); return Math.round((n-m)*i+m); } function getRandomArr(m,n,l){ //m：生成随即整数的最小值，n：生成随即整数的最大值，l：生成的数组的长度 var resultArr=[]; for(var i=0;i<l;i++){ resultArr.push(rand(m,n)) } return resultArr; } function partition(a,st,en) { var s=st; var e=en+1; var temp=a[s]; while(1) { while(a[++s]<＝temp); while(a[--e]>temp); if(s>e)break; var tem=a[s]; a[s]=a[e]; a[e]=tem; } a[st]=a[e]; a[e]=temp; return e; } function doSort(a,s,e) { if(s<e) { var pos=partition(a,s,e); doSort(a,s,pos-1); doSort(a,pos+1,e); } } Array.prototype.quickSort = function() { doSort(this,0,this.length-1); } function sortIntF(a,b){return a-b} function pk(num){ //num: 用于排序的数组的元素个数 //生成用于排序的数组 var arr=getRandomArr(1,999999,num); //当元素个数小于10000时，执行n次取平均值 var n=Math.ceil(10000/num); //生成多个用于排序的数组的拷贝 var quickSortArrs=[]; var sortArrs=[]; for(var i=0;i<n;i++){ quickSortArrs.push(arr.slice(0)); sortArrs.push(arr.slice(0)); } var t1=new Date(); for(var i=0;i<n;i++){ quickSortArrs[i].quickSort(); } var t2=new Date(); for(var i=0;i<n;i++){ sortArrs[i].sort(sortIntF); } var t3=new Date(); alert("性能比较，对于"+num+"个元素的数组，平均每次排序花费时间如下：\n" +"Array.prototype.sort："+((t3-t2)/n)+"ms\n" +"quickSort："+((t2-t1)/n)+"ms\n" ); alert("排序结果是否正确："+(sortArrs[0].join()==quickSortArrs[0].join())); } pk(500); pk(2000); pk(30000); </script>