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 fast sort algorithm. I was very depressed when I saw it because I spent a long time on the sort algorithm and actually forgot the sort method of Array itself.
But is the built-in sort method in javascript really faster than the quick sorting algorithm?
Haha, you'll know if you test it
Let me first talk about the environment I tested
1. My testing environment is IE6.0 and firefox2.0
2. Each algorithm has many different implementation methods. In the following test, I chose the quick sorting algorithm implemented by netizens above, but just moved the embedded functions outside.
3. The speed of algorithm execution is related to the type, size, and amount of data. I will only compare the sorting of integers smaller than 9999999, and the data volume is set to 500, 2000, and 30000, respectively.
About the sort method: the sort method is a built-in method of Array: The authoritative javascript guide is defined as follows:
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 to customize its own sorting logic. When no parameters are provided, the default sorting is in character order. Therefore, a function-type parameter needs to be provided for integer sorting. The calling method of this test is as follows:
(function(a,b){return a-b})
Of course, if the number of integer digits to be sorted is the same, the result returned without providing parameters is the same. Just test it and you will know:
<script>
alert( [3,4,5,11,1].sort())
alert([3,4,5,11,1].sort(function(a,b){return a-b}))
</script>
Tip: You can modify it first and then run it
The result is [1, 11, 3, 4, 5], which is obviously not the result we want
Generate arrays that need to be sorted. In order to get a fair result, I will randomly generate the arrays used for sorting. The arrays used by both methods in each comparison have the same elements. Here is the code to generate a random array.
function random(m,n){
//Generate an integer between m and n
var i=();
return ((n-m)*i+m);
}
function getRandomArr(m,n,l){
//m: generate the minimum value of the instant integer, n: generate the maximum value of the instant integer, l: the length of the generated array
var resultArr=[];
for(var i=0;i<l;i++){
(random(m,n))
}
return resultArr;
}
The implementation of the quick sorting algorithm is taken from the implementation of this netizen on the 51js forum I saw. The code is as follows:
function doSort(a,s,e)
{
if(s<e)
{
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]<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(this,0,-1);
}
Check whether the results are correctly used () to judge. The performance test code is as follows:
function sortIntF(a,b){return a-b}
function pk(num){
//num: The number of elements of the array used to sort
//Generate an array for sorting
var arr=getRandomArr(1,999999,num);
//When the number of elements is less than 10,000, perform n times to take the average value
var n=(10000/num);
// Generate multiple copies of arrays for sorting
var quickSortArrs=[];
var sortArrs=[];
for(var i=0;i<n;i++){
((0));
((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("Performance comparison, for arrays of "+num+" elements, the average time spent per sort is as follows:\n"
+"："+((t3-t2)/n)+"ms\n"
+"quickSort："+((t2-t1)/n)+"ms\n"
);
alert("Is the sorting result correct: "+(sortArrs[0].join()==quickSortArrs[0].join()));
}
Just call the pk function directly. For example, you need to compare the sorting performance of an array of 300 elements, and just call pk(300)
The complete test code is as follows:
[Ctrl+A Select all Note:Introducing external Js requires refreshing the page before execution]
Test results
First First First First (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 407
As can be seen from the results,
In ie6.0, the quick sorting algorithm is much faster than the sort method of Array objects. For fewer elements, the speed of quick sorting is basically about 5 times that of the sort method. For 30,000 elements, the quick sorting is more than ten times that of the sort method
In ff2.0, the two sorting algorithms are basically the same speed, and the quick sorting algorithm is a little faster. This also shows that the sort of Array object in ff2.0 is relatively efficient. Maybe it is used to use quick sort because it is very close to the data of the quick sorting algorithm.
Note: The above test only represents the test results on my machine. Maybe there will be a big difference in the results on your machine. I hope everyone can also help test it.