In my last article, I summarized the JavaScript implementations of six sorting algorithms, as well as the ideas behind each algorithm. Many of my friends on Nuggets have come up with some good ideas or optimized methods. Here are some new tests for these methods to verify their claims. In addition, THANK you very much for reading my article carefully. Your opinions have made me make great progress. At the same time, I have realized many shortcomings of myself.

First of all, to facilitate the test, we wrote a random number group generation function, the code is as follows:

exports.generateArray = function(length) {
    let arr = Array(length);
    for(let i=0; i<length; i++) {
        arr[i] = Math.random();
    }
    return arr;
};
Copy the code

As long as you input the length of the array, you can get a set of random numbers that meet the requirements for you to test.

Which is faster than the native interface?

This is an idea by @jhanlu. It’s a really good idea. Put it to the test here. The comparison objects are the array.prototype. sort method and quicksort.

Test native methods:

console.time('RawSort');
const arr = generateArray(10000000);
arr.sort((a, b) => a - b);
console.timeEnd('RawSort');
Copy the code

It takes 12.7s to sort 10000000 (10 million) pieces of data from small to large:

RawSort: 12653.942 msCopy the code

Sort 10000 (ten thousand) pieces of data, 0.023 seconds:

RawSort: 23.382 msCopy the code

Test fast platoon:

The code is as follows:

function quickSort(arr) {
    let left = 0,
        right = arr.length - 1;
    console.time('QuickSort');
    main(arr, left, right);
    console.timeEnd('QuickSort');
    return arr;
    function main(arr, left, right) {
        if(arr.length === 1) {
            return;
        }
        let index = partition(arr, left, right);
        if(left < index - 1) {
            main(arr, left, index - 1);
        }
        if(index < right) {
            main(arr, index, right);
        }
    }
    function partition(arr, left, right) {
        let pivot = arr[Math.floor((left + right) / 2)];
        while(left <= right) {
            while(arr[left] < pivot) {
                left++;
            }
            while(arr[right] > pivot) {
                right--;
            }
            if(left <= right) {
                [arr[left], arr[right]] = [arr[right], arr[left]];
                left++;
                right--;
            }
        }
        return left;
    }
}

console.log(quickSort(generateArray(10000000)));
Copy the code

It takes 3.6s to sort 10000000 (10 million) pieces of data from smallest to largest:

QuickSort: 3632.852 msCopy the code

Sorting for 10000 (10,000) pieces of data takes 0.012s:

QuickSort: 12.482 msCopy the code

It can be seen that regardless of large or small data volume, manual fast row is faster, but the advantage is not great. The guess is that the native method actually calls the underlying quicksort for sorting, which is slightly slower because of an extra layer of encapsulation than manual quicksort.

For the native method, but also to understand, found that the V8 engine is unstable sort, it according to the array length to choose the sort algorithm. When the array length is less than 10, insert sort is used. The array.prototype.sort () method is used for quick sorting when the Array length is above 10. .

It can be found from the above conclusion that when the data volume to be sorted at the front end is relatively large (tens of millions of levels, of course, it is almost impossible), it is best to use the manual implementation of fast sorting, which will be faster. Array.prototype.sort can be used to sort a small amount of data. After all, the time difference between ten million pieces of data is no more than two seconds. While the native approach is fine for us, this is by no means a reason for front-end engineers not to learn about sorting and algorithms.

Bubble sort write wrong?

In the previous article, I also write on the second cycle from the beginning to the end of the traversal, but @ of snow dance , can be optimized, because no traversal data at a time, meet the requirements of the data is automatically sort to the end of the maximum sort (such as the first round the last position), so in after traversal, can ignore the item after I array, That’s the right thing to do. Here’s a comparison:

From the previous article:

function bubbleSort(arr) { console.time('BubbleSort'); let len = arr.length; let count = 0; Arr. ForEach (() => {// I < len-1 should actually be I < len-1 -i. for(let i=0; i<len-1; i++) { if(arr[i] > arr[i+1]) { let tmp = arr[i+1]; arr[i] = tmp; arr[i+1] = arr[i] } count++; }}); console.timeEnd('BubbleSort'); return count; } console.log(bubbleSort(generateArray(20000)));Copy the code

The test sequencing of 20,000 (20,000) pieces of data takes 1.27s:

The BubbleSort: 1277.692 msCopy the code

After improving the code:

function bubbleSort(arr) { console.time('BubbleSort'); let len = arr.length; let count = 0; arr.forEach(() => { for(let i=0; i<len-1-i; i++) { if(arr[i] > arr[i+1]) { let tmp = arr[i+1]; arr[i] = tmp; arr[i+1] = arr[i] } count++; }}); console.timeEnd('BubbleSort'); return count; } console.log(bubbleSort(generateArray(20000)));Copy the code

Test 20,000 (20,000) pieces of data, taking 0.64s:

The BubbleSort: 638.900 msCopy the code

You can see that the time is almost halved.

Three, the selection sort is not good enough!

Here is, indeed, I was lazy, every time the best way is traverse to find the minimum (or maximum) to a variable, and each time I am found less than or greater than reference elements will switch them, although this time complexity did not change, but the variable exchange cost more time, cause the loss of performance, Thank you @ly578269725 for your guidance. I apologize for any misunderstanding caused by my laziness. Here are the measured results:

Lazy writing:

function selectionSort(arr) { console.time('SelectionSort'); let len = arr.length; let count = 0; arr.forEach((item, index) => { for(let i=index; i<len; i++) { if(arr[i] > arr[index]) { [arr[index], arr[i]] = [arr[i], arr[index]]; } count++; }}); console.log(arr); console.timeEnd('SelectionSort'); return count; } console.log(selectionSort(generateArray(30000)));Copy the code

It takes 5.2s to sort 20,000 (20,000) pieces of data:

SelectionSort: 5227.515 msCopy the code

After improvement:

function selectionSort(arr) {
    console.time('SelectionSort');
    let len = arr.length;
    let count = 0;
    arr.forEach((item, index) => {
        let min = index;
        for(let i=index; i<len; i++) {
            if(arr[i] < arr[index]) {
                min = i;
            }
            count++;
        }
        if(min !== index) {
            [arr[min], arr[index]] = [arr[index], arr[min]];
        }
    });
    console.log(arr);
    console.timeEnd('SelectionSort');
    return count;
}

console.log(selectionSort(generateArray(20000)));
Copy the code

It takes 1.25s to sort 20,000 (20,000) pieces of data:

SelectionSort: 1250.662 msCopy the code

You can see a real performance improvement, and you can also see that swapping values is more expensive than assigning values.

Four, ruan teacher’s quick row wrong?

The Javascript implementation of Quicksort is a reference to this article. Ruan teacher about this article is wrong, zhihu had the answer: how to look at the article “interviewer: Ruan Yifeng version of the quicksort is completely wrong”? “, including Liao Xuefeng and other bigwigs said there was no big problem with Teacher Ruan’s article, at least not completely wrong! Ruan wrote this article in 2011, when he was not a programmer at all, and his article is more about ideas than code. Through Ruan’s explanation, you can easily understand what is going on in quicksorting, and say what is wrong with him. The array.prototype. splice method is used to delete the pivot element from the Array and retrieve the pivot element. This method increases the complexity of the algorithm, and the code implemented is not optimal. But that’s not to say that his code is completely the wrong reason, algorithm is thought more than the code, you could say that his code is not good (in fact is for beginners, the code better understand), but can’t say his code is completely wrong, because he is completely comply with the core idea of quick sort: partition. Be like what liao Xuefeng teacher says is same: somebody else course basically is to speak train of thought, the basic idea of quick platoon is divide rule. Array.sort()

In fact, Ruan teacher in his website JavaScript standard reference tutorial (alpha), has long realized the optimization of quick sorting, blog time is January 30, 2013, really when people don’t understand?