The twentieth and final article in the JavaScript series reads v8 sorting source code
preface
V8 is Chrome’s JavaScript engine, and the sorting of arrays is implemented entirely in JavaScript.
The sorting algorithm depends on the length of the array. When the array length is less than or equal to 10, insert sort is used. When the array length is greater than 10, quick sort is used. (Not exactly, of course).
Let’s look at insert sort and quicksort first.
Insertion sort
The principle of
Treat the first element as an ordered sequence, iterate through the array, and insert subsequent elements into the constructed ordered sequence.
graphic
implementation
function insertionSort(arr) {
for (var i = 1; i < arr.length; i++) {
var element = arr[i];
for (var j = i - 1; j >= 0; j--) {
var tmp = arr[j];
var order = tmp - element;
if (order > 0) {
arr[j + 1] = tmp;
} else {
break;
}
}
arr[j + 1] = element;
}
return arr;
}
var arr = [6.5.4.3.2.1];
console.log(insertionSort(arr));Copy the codeTime complexity
Time complexity refers to the computational workload required to execute the algorithm, which examines the situation when the size of the input value approaches infinity. In general, the number of repeated execution of basic operations in the algorithm is a function of the problem size N.
Best case: array ascending, time complexity: O(n)
Worst case: Array in descending order, time complexity: O(n²)
The stability of
Stability refers to whether the same elements remain in opposite positions after sorting.
It should be noted that for the unstable sorting algorithm, as long as an example is given, it can show its instability; For stable sorting algorithm, it is necessary to analyze the algorithm to obtain stable characteristics.
For example, [3, 3, 1], after sorting, still [3, 3, 1], but actually the second 3 comes before the first 3, then this is an unstable sorting algorithm.
Insertion sort is a stable algorithm.
advantage
Insertion sort is more efficient when the array is near sorted or the problem size is small. This is why V8 uses insert sort when the array length is 10 or less.
Quick sort
The principle of
- Select an element as the “base”
- Anything less than the baseline is moved to the left of the baseline; Anything greater than the base is moved to the right of the base.
- For the two subsets to the left and right of the base, repeat steps 1 and 2 until there is only one element left in all the subsets.
The sample
The example and the following implementation are from “Javascript Implementation of Quicksort” by Ruan Yifeng.
Take arrays [85, 24, 63, 45, 17, 31, 96, 50] as an example:
First, select the middle element 45 as the “baseline”. (The base value can be chosen arbitrarily, but the middle value is easier to understand.)
The second step is to compare each element to the “base” in order to form two subsets, one “less than 45″ and one” greater than or equal to 45″.
Third, repeat steps 1 and 2 for both subsets until there is only one element left in all subsets.
implementation
var quickSort = function(arr) {if (arr.length <= 1) { return arr; }
// Take the middle element of the array as the base
var pivotIndex = Math.floor(arr.length / 2);var pivot = arr.splice(pivotIndex, 1) [0];varleft = [];varright = [];for (var i = 0; i < arr.length; i++){if(arr[i] < pivot) { left.push(arr[i]); }else{ right.push(arr[i]); }}return quickSort(left).concat([pivot], quickSort(right));
};Copy the codeHowever, this implementation requires extra space to store the left and right subsets, so there is also an implementation of in-place sorting.
graphic
Let’s look at the implementation diagram of sort in place:
Just to give you an idea of how quicksort works, I’ve slowed it down.
In this diagram, the baseline is evaluated by taking the leftmost element, yellow for the current baseline, green for elements less than the baseline, and purple for elements greater than the baseline.
We will see that the green element is immediately to the right of the base, the purple element is moved to the back, and then the base and the last green element are swapped, so that the base is in the correct position, that is, the first element is less than the base, and the last element is greater than the base. And then the front and the back of the multiple elements base, do sort.
The in – place
function quickSort(arr) {
// Swap elements
function swap(arr, a, b) {
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
function partition(arr, left, right) {
var pivot = arr[left];
var storeIndex = left;
for (var i = left + 1; i <= right; i++) {
if (arr[i] < pivot) {
swap(arr, ++storeIndex, i);
}
}
swap(arr, left, storeIndex);
return storeIndex;
}
function sort(arr, left, right) {
if (left < right) {
var storeIndex = partition(arr, left, right);
sort(arr, left, storeIndex - 1);
sort(arr, storeIndex + 1, right);
}
}
sort(arr, 0, arr.length - 1);
return arr;
}
console.log(quickSort(6.7.3.4.1.5.9.2.8))Copy the codeThe stability of
Quicksort is an unstable sort. If you want to prove that a sort is unstable, all you have to do is give an example.
So let’s give an example
Take array [1, 2, 3, 3, 4, 5] as an example, because the selection of datum is uncertain, if the third element (i.e. the first 3) is selected as the datum, all elements less than 3 are in the front, and those greater than or equal to 3 are in the back, the sorting result is no problem. However, if a fourth element (the second 3) is selected, the first 3 will be moved after the second 3, so quicksort is an unstable sort.
Time complexity
Ruan yifeng teacher’s implementation, the benchmark is to take the middle element, and in situ sorting the benchmark is to take the leftmost element. The key point of quicksort is the selection of the benchmark. Different benchmarks will have different performance.
The best time complexity for quicksort is O(nlogn), but why nlogn? Here’s a loose proof:
In the best case, the entire array is bisected each time. Assuming that the array has N elements, the recursion depth is log2n + 1, and the time complexity is O(n)[(log2n + 1)]. Because the time complexity examines the situation when the input value approaches infinity, the low-order term will be ignored, and the time complexity is O(nlog2n).
If the running time of a program is logarithmic, it will slow down as n increases. If the base is 10, log 1000 is 3, and if n is 1,000,000, log n is 6, which is only twice as much. If the base number is 2, the value of log21000 is about 10, and the value of log21000000 is about 19, which is about twice as large as before. We can see that a logarithm function of any base is different by a constant factor. So we think O(logn) is enough to express the logarithm of all bases, so the time complexity is O(nlogn).
In the worst-case scenario, if the first or last element is selected each time for a sorted array, a subset will be empty each time, and the number of recursive levels will reach N, resulting in the time complexity of the algorithm being reduced to O(n²).
This illustrates how important the choice of a benchmark is, and v8 has done a lot to optimize it for better performance.
V8 benchmark selection
V8’s principle for selecting a base is to select one element beyond the beginning and the end, and then sort the three values to the middle.
When the array length is greater than 10 but less than 1000, take the middle element, implementation code is as follows:
// The index of the benchmark
// >> 1 is equal to dividing by 2 (ignore remainder)
third_index = from + ((to - from) > >1);Copy the codeWhen the array length is greater than 1000, take a value every 200 ~ 215 elements, and then sort these values, take the subscript of the middle value, the code is as follows:
// It is simple
function GetThirdIndex(a, from, to) {
var t_array = new Array(a);// The & bit operator
var increment = 200 + ((to - from) & 15);
var j = 0;
from+ =1;
to -= 1;
for (var i = from; i < to; i += increment) {
t_array[j] = [i, a[i]];
j++;
}
// Sort the randomly selected values
t_array.sort(function(a, b) {
return comparefn(a[1], b[1]);
});
// take the subscript of the intermediate value
var third_index = t_array[t_array.length >> 1] [0];
return third_index;
}Copy the codeYou might be wondering what 200 + ((to-from) & 15) means.
The & represents bitwise and, performing a Boolean and operation bit by bit on the integer operands. Only if the corresponding bits of the two operands are 1, this bit in the result is 1.
Take 15 & 127 as an example:
15 Binary: (0000 1111)
127 binary :(1111 1111)
The bitwise result is :(0000 1111) = 15
So 15 over 127 is equal to 15.
Note that the binary value of 15 is: 1111, which means that any bitwise sum of and 15 is less than or equal to 15, thus achieving a value every 200-215 elements.
V8 source
Finally it’s time to see the source code! Source address: github.com/v8/v8/blob/… .
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];
var order = comparefn(tmp, element);
if (order > 0) {
a[j + 1] = tmp;
} else {
break;
}
}
a[j + 1] = element; }};function QuickSort(a, from, to) {
var third_index = 0;
while (true) {
// Insertion sort is faster for short arrays.
if (to - from< =10) {
InsertionSort(a, from, to);
return;
}
if (to - from > 1000) {
third_index = GetThirdIndex(a, from, to);
} else {
third_index = from + ((to - from) > >1);
}
// Find a pivot as the median of first, last and middle element.
var v0 = a[from];
var v1 = a[to - 1];
var v2 = a[third_index];
var c01 = comparefn(v0, v1);
if (c01 > 0) {
// v1 < v0, so swap them.
var tmp = v0;
v0 = v1;
v1 = tmp;
} // v0 <= v1.
var c02 = comparefn(v0, v2);
if (c02 >= 0) {
// v2 <= v0 <= v1.
var tmp = v0;
v0 = v2;
v2 = v1;
v1 = tmp;
} else {
// v0 <= v1 && v0 < v2
var c12 = comparefn(v1, v2);
if (c12 > 0) {
// v0 <= v2 < v1
vartmp = v1; v1 = v2; v2 = tmp; }}// v0 <= v1 <= v2
a[from] = v0;
a[to - 1] = v2;
var pivot = v1;
var low_end = from + 1; // Upper bound of elements lower than pivot.
var high_start = to - 1; // Lower bound of elements greater than pivot.
a[third_index] = a[low_end];
a[low_end] = pivot;
// From low_end to i are elements equal to pivot.
// From i to high_start are elements that haven't been compared yet.
partition: for (var i = low_end + 1; i < high_start; i++) {
var element = a[i];
var order = comparefn(element, pivot);
if (order < 0) {
a[i] = a[low_end];
a[low_end] = element;
low_end++;
} else if (order > 0) {
do {
high_start--;
if (high_start == i) break partition;
var top_elem = a[high_start];
order = comparefn(top_elem, pivot);
} while (order > 0);
a[i] = a[high_start];
a[high_start] = element;
if (order < 0) { element = a[i]; a[i] = a[low_end]; a[low_end] = element; low_end++; }}}if (to - high_start < low_end - from) {
QuickSort(a, high_start, to);
to = low_end;
} else {
QuickSort(a, from, low_end);
from= high_start; }}}var arr = [10.9.8.7.6.5.4.3.2.1.0];
function comparefn(a, b) {
return a - b
}
QuickSort(arr, 0, arr.length)
console.log(arr)Copy the codeWe analyze the execution process using arrays [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] as an example.
1. Run the QuickSort function whose from value is 0 and to value is 11.
2.10 < to-from < 1000 The subscript of the third base element is (0 + 11 >> 1) = 5, and the base value A [5] is 5.
Select * from a[0] a[10] A [5]; select * from a[0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10];
Swap the first element of the array (from + 1) with the second element of the array (0, 5, 8, 7, 6, 9, 4, 3, 2, 1, 10). The first element of the array (from + 1) is less than 5. The following elements are unsorted.
So what we’re going to do is we’re going to put everything that’s less than 5 in front of 5.
5. Then we enter the partition loop, we still take this array as an example, separate out to write a demo
// Assuming the code executes at this point, let's just set the low_end and other variables for demonstration purposes
// You can copy it directly to the browser to see the effect of the array transform
var a = [0.5.8.7.6.9.4.3.2.1.10]
var low_end = 1;
var high_start = 10;
var pivot = 5;
console.log('The starting array is', a)
partition: for (var i = low_end + 1; i < high_start; i++) {
var element = a[i];
console.log('The current element of the loop is:', a[i])
var order = element - pivot;
if (order < 0) {
a[i] = a[low_end];
a[low_end] = element;
low_end++;
console.log(a)
}
else if (order > 0) {
do {
high_start--;
if (high_start == i) break partition;
var top_elem = a[high_start];
order = top_elem - pivot;
} while (order > 0);
a[i] = a[high_start];
a[high_start] = element;
console.log(a)
if (order < 0) {
element = a[i];
a[i] = a[low_end];
a[low_end] = element;
low_end++;
}
console.log(a)
}
}
console.log('The final result is', a)
console.log(low_end)
console.log(high_start)Copy the codeA [I] = a[I] = a[I] = a[I] = a[I] = a[I] The purpose of the do while loop is to find the elements in reverse order, find the first element that is less than the reference value, and then swap that element with a[I]. The first element less than the reference value is 1, then 1 is swapped with 8, and the array becomes [0, 5, 1, 7, 6, 9, 4, 3, 2, 8, 10]. The high_start value is used to record where the reverse lookup is.
The array is [0, 1, 5, 7, 6, 9, 4, 3, 2, 8, 10]. The value of low_end is increded by 1.
The array becomes [0, 1, 5, 2, 6, 9, 4, 3, 7, 8, 10] and then becomes [0, 1, 2, 5, 6, 9, 4, 3, 7, 8, 10].
[0, 1, 2, 5, 3, 9, 4, 6, 7, 8, 10] and then [0, 1, 2, 3, 5, 9, 4, 6, 7, 8, 10]
The array becomes [0, 1, 2, 3, 5, 4, 9, 6, 7, 8, 10] and then becomes [0, 1, 2, 3, 4, 5, 9, 9, 6, 7, 8, 10].
11. In the next iteration, because I == high_start, it means that the forward and backward lookups are finally found together, and the following elements must be greater than the base value, then exit the loop
12. The result after traversal is [0, 1, 2, 3, 4, 5, 9, 6, 7, 8, 10], the elements before the reference value 5 are all less than 5, and the elements after are all greater than 5. Then we QuickSort the two subsets respectively
Low_end = 5, high_start = 6, to = 10, from = 0, to-high_start < low_end – from = true We do QuickSort(a, 6, 10), which sorts the elements that follow, but notice that in the new QuickSort, since from-to is less than 10, we’re actually using insert sort this time. So to be precise, V8 uses a mixture of quicksort and insert sort when the array length is greater than 10.
InsertionSort(a, 0, 5); insert sort (a, 0, 5); insert sort (a, 0, 5); insert sort (a, 0, 5);
15. The while loop ends because there is a return statement in the statement to-from <= 10.
16. V8 does a quick sort of the array, then inserts the two subsets separately, and finally changes the array to the correctly sorted array.
To compare
To get a feel for insert sort and quicksort:
Photos come from www.toptal.com/developers/…
series
JavaScript Thematic series directory address: github.com/mqyqingfeng… .
The JavaScript series is expected to write about 20 articles, focusing on the implementation of some function points in daily development, such as anti-shaking, throttling, de-weighting, type judgment, copy, maximum value, flat, Currie, recursion, out-of-order, sorting, etc. (Chao) (XI) underscore and jQuery underscore
If there is any mistake or not precise place, please be sure to give correction, thank you very much. If you like or are inspired by it, welcome star and encourage the author.