This is the 9th day of my participation in Gwen Challenge

The paper come zhongjue shallow, must know this to practice!

In the last article, we walked through the basic use of the arr.sort() method:

const arr = [49.5.14.89.71.3.10];

//
arr.sort(function (a, b) {
    return a - b;   // In ascending order
});

// Arrow function
arr.sort((a, b) = > a - b);

// Results [3, 5, 10, 14, 49, 71, 89]
Copy the code

Use to use, it is not difficult to copy, we daily also write so, no problem! But if a method is not thoroughly researched, it is easy to step on potholes and often fails to fill the potholes!

Today, we will focus on the comparison function compareFunction.

To make things a little bit smoother, let’s take a look at insertion sort before we look at comparison functions.

Insertion sort

Insertion Sort algorithm is a simple and intuitive sorting algorithm. It works by building an ordered sequence, scanning back to front in the sorted sequence for unsorted data, finding the appropriate location and inserting it.

Algorithm description:

In general, insert sort is implemented using in-place arrays:

  • Starting with the first element, the element can be considered sorted;
  • Fetch the next element and scan back to front in the sorted element sequence;
  • If the element (sorted) is larger than the new element, move the element to the next position;
  • Repeat step 3 until you find a place where the sorted element is less than or equal to the new element;
  • After inserting a new element into that position;
  • Repeat steps 2 to 5.

GIF demo:

Starting with the second element in the array (the first element is sorted by default), each element acts as a swim-value and is compared to the (sorted) element before it. If the swim-value is small, the element being compared is moved one bit further forward. Otherwise, the cursor value is inserted after the comparison value to end the comparison.

On the comparison functioncompareFunction

If you want the sort() method to sort by certain rules (such as numeric size), you need to specify the compareFunction.

If compareFunction is specified, the array is sorted by the value returned from calling the function. It takes two arguments, a and b, and returns the following values:

  • If compareFunction(a, b) is less than 0, then A is placed before B.

  • If compareFunction(a, b) is equal to 0, the relative positions of a and B remain the same.

  • If compareFunction(a, b) is greater than 0, b will be placed before A.

  • CompareFunction (a, b) must always return the same comparison result on the same input, otherwise the sorting result will be indeterminate.

Preliminary exploration of compareFunction

Instead of doing any complicated analysis, let’s use the console to print out what a and B are:

const arr = [49.5.14.89.71.3.10];
console.log(arr);
let times = 0;
let res = [];
arr.sort((a, b) = > {
    res.push({times, a, b, "a - b": a - b});
    times++;
    return a - b;
});
console.log(res);
console.log(arr);
Copy the code

The result is as follows:

From the above picture, we can see:

  • The values of A are in the order of the original array, which should be sorted by insertion.
  • I think a stands for cursor.
  • From the change of b value, it can be seen that the dichotomy method is adopted when A finds its position for the first time. If a < B, it compares forward, and if a> B, it compares backward.

So, whether the mechanism is such a process as we see needs further investigation.

CompareFunction delves deeper

What better way to get to the bottom of a problem than to get to the root of it? So let’s take a look at the source code of the V8 engine and see how it implements sort.

The source code below is from V8 prior to version 7.2, and the array sorting implementation has changed considerably since then.

In the array.js file, the code about the implementation of sort interface is as follows:

function InnerArraySort(array, length, comparefn) {
    // In-place QuickSort algorithm.
    // For short (length <= 22) arrays, insertion sort is used for efficiency.

    if(! IS_CALLABLE(comparefn)) { comparefn =function (x, y) {
            if (x === y) return 0;
            if (% _IsSmi(x) && % _IsSmi(y)) {
                return % SmiLexicographicCompare(x, y);
            }
            // Convert an array element to a string
            x = TO_STRING(x);
            y = TO_STRING(y);
            if (x == y) return 0;
            else return x < y ? -1 : 1;
        };
    }
    var InsertionSort = function InsertionSort(a, from, to) {
        for (var i = from + 1; i < to; i++) {
            var element = a[i];
            for (var j = i - 1; j >= from; j--) {
                var tmp = a[j];
                // Call comparison functions a: TMP, b: element
                var order = comparefn(tmp, element);
                if (order > 0) {
                    a[j + 1] = tmp;
                } else {
                    break;
                }
            }
            a[j + 1] = element; }};/*** some code here **/ 

    var QuickSort = function QuickSort(a, from, to) {
        /*** some code here **/ 
    };
}

function ArraySort(comparefn) {
  	CHECK_OBJECT_COERCIBLE(this."Array.prototype.sort");

  	var array = TO_OBJECT(this);
  	var length = TO_LENGTH(array.length);
  	return InnerArraySort(array, length, comparefn);
}

// I will not put the source code, you are interested in research, you can click on the above link to view
Copy the code

Code analysis:

  1. When sort() is implemented in V8, there are two kinds of sorting methods: “insert sort” and “quicksort”.
  2. For short arrays (length <= 22), insert sort is more efficient.
  3. If it doesn’t come incomparefn, generates onecomparefnCompare functions.
  4. In an automatically generated comparison function, the array elements passed are passedTO_STRINGMethod to a string, then a line comparison.
  5. The b in the compare function is the cursor value, which is different from the latest version of Chrome.

The function we passed in the sort method is used here:

var order = comparefn(tmp, element);
Copy the code

Sort the array according to the return value of the function we passed in:

if (order > 0) {
    a[j + 1] = tmp;
} else {
    break;
}
Copy the code
  • If you return a value(a - b)Greater than 0, that isa > b, copies the current comparison value, A, to its next bit, and continues the comparison forward using the cursor value, B.
  • If the return value is less than or equal to 0, the comparison is ended and the vernal value B is inserted after the last comparison value A.

conclusion

In both older and more recent versions of V8, the results returned by sort() have not changed, but the internal implementation mechanism has changed (certainly for the better).

To make sure that sort() returns the expected result, we pass it a function as a comparison rule.

In the comparison function, due to the different v8 versions, the implementation mechanism is different, leading to its parameter meaning is not the same, so we do not need to care about the specific meaning of its parameters for the moment.

The comparison function, if written completely, would be:

arr.sort((a,b) = > {
    const res = a - b;
    return res > 0 ? 1 : (res < 0 ? -1 : 0 );
});
Copy the code

Strictly speaking, the comparison function returns only three values: -1, 0, and 1.

Return a – b is in ascending order, and return b – a is in descending order.

To finish this article

Learn interesting knowledge, meet interesting friends, shape interesting soul!

Everybody is good! I am the author of programming Samadhi, yi Wang, my public account is “programming Samadhi”, welcome to pay attention to, I hope you can give me more advice!

Knowledge and skills should be paid equal attention to, internal force and external power should be repaired simultaneously, theory and practice should grasp both hands, both hands should be hard!