preface
This paper mainly introduces several kinds of sorting algorithms commonly used in JS, and analyzes the strategy of SORT implementation with the relevant source code in V8
Common sorting algorithms
First, review the two elements that sorting algorithm needs to pay attention to
Time complexity
Describe the running time of the algorithm, usually described by big O, with a time complexity graph to help understand
Spatial complexity
Measures how much storage space an algorithm takes while running
Common sort
The top ten common sorting algorithms are not here, but can be classified from different angles according to their properties
-
Comparison based or not: Comparison sorting and non-comparison sorting
-
Stable or not: Stable class sort and unstable class sort
Usually we categorize in terms of whether or not we categorize in terms of ranking
-
Comparison sort
The relative order of elements is determined by comparison, and its time complexity cannot break O(Nlogn), so it is also called nonlinear time comparison sort.
-
Non-comparison class sorting
Instead of determining the relative order of elements by comparison, it can break through the time lower bound based on comparison sorting and run in linear time, so it is also called linear time non-comparison sort.
Specific classification enumeration can be understood with the following figure
So let’s write down a couple of common classical sorts
Quick sort
Quicksort mainly uses the idea of recursive branching. Through sorting, the records to be sorted are separated into two independent parts. If the keywords of one part of the records are smaller than those of the other part, the records of the two parts can be sorted to achieve the order of the whole sequence.
var a = [ 25.76.34.232.6.456.221];
function quickSort(array) {
var quick = function(arr) {
if (arr.length <= 1) return arr
const index = Math.floor(len >> 1)
const pivot = arr.splice(index, 1) [0]
const left = []
const right = []
for (let i = 0; i < arr.length; i++) {
if (arr[i] > pivot) {
right.push(arr[i])
} else if (arr[i] <= pivot) {
left.push(arr[i])
}
}
return quick(left).concat([pivot], quick(right))
}
const result = quick(array)
return result
}
quickSort(a);// [6, 25, 34, 76, 221, 232, 456]
Copy the codeHeap sort
Heap sort is a sort algorithm designed by using heap data structure. Heap is a nearly complete binary tree structure and also satisfies the property of heap, that is, the key value or index of the child node is always smaller than (or greater than) its parent node. The bottom layer of the heap is essentially a complete binary tree, which can be implemented using arrays.
The heap with the largest root node is called the large root heap, and the heap with the smallest root node is called the small root heap. You can sort the heap from largest to smallest, or from smallest to largest, respectively. Look at the code below.
var a = [25.76.34.232.6.456.221];
function heap_sort(arr) {
var len = arr.length
var k = 0
function swap(i, j) {
var temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
function max_heapify(start, end) {
var dad = start
var son = dad * 2 + 1
if (son >= end) return
if (son + 1 < end && arr[son] < arr[son + 1]) {
son++
}
if (arr[dad] <= arr[son]) {
swap(dad, son)
max_heapify(son, end)
}
}
for (var i = Math.floor(len / 2) - 1; i >= 0; i--) {
max_heapify(i, len)
}
for (var j = len - 1; j > k; j--) {
swap(0, j)
max_heapify(0, j)
}
return arr
}
heap_sort(a); // [6, 25, 34, 76, 221, 232, 456]
Copy the codeMerge sort
Merge sort is an effective sorting algorithm based on merge operation, which is a very typical application of divide-and-conquer. The ordered subsequences are combined to obtain a fully ordered sequence. Order each subsequence first, and then order the segments of the subsequence. If two ordered tables are merged into one ordered table, it is called binary merge.
var a = [25.76.34.232.6.456.221];
function mergeSort(array) {
const merge = (right, left) = > {
const result = []
let il = 0
let ir = 0
while (il < left.length && ir < right.length) {
if (left[il] < right[ir]) {
result.push(left[il++])
} else {
result.push(right[ir++])
}
}
while (il < left.length) {
result.push(left[il++])
}
while (ir < right.length) {
result.push(right[ir++])
}
return result
}
const mergeSort = array= > {
if (array.length === 1) { return array }
const mid = Math.floor(array.length / 2)
const left = array.slice(0, mid)
const right = array.slice(mid, array.length)
return merge(mergeSort(left), mergeSort(right))
}
return mergeSort(array)
}
mergeSort(a); // [6, 25, 34, 76, 221, 232, 456]
Copy the codeFinally, a statistical comparison table of each sorting algorithm is attached:
Sort method in js
The sort method is basically used
arr.sort([compareFunction])
If you don’t pass in compareFunction, elements are sorted by the Unicode loci of each character converted to a string. Some students often make mistakes with integer sorting, mostly because they omit this rule
const names = ['tom'.'jesse'.'jack'];
names.sort();
console.log(names);
// ["jack", "jesse", "tom"]
const array1 = [1.30.4.21.100000];
array1.sort();
console.log(array1);
// [1, 100000, 21, 30, 4]
Copy the codeIf the compareFunction argument is specified, then the array is sorted by the value returned from calling the function, i.e. a and B are the two elements to be compared:
- CompareFunction (a, b) < 0, a will be sorted before B
- CompareFunction (a, b) === 0
- CompareFunction (a, b) > 0, b will be placed before A
Sort source code analysis
For the number of elements to be sorted, n, the specific sorting strategy has several scenarios:
- When n is less than or equal to 10, this parameter is used
Insertion sort; - When n is greater than 10, this parameter is used
Three-way quicksort; - 10
- N >1000, pick one element every 200-215, place it in a new array, and sort it to find the middle number as the median.
There are two questions you might struggle with at first glance
1. Why use quicksort when there are fewer elements
In fact, a careful analysis of the reasons is not difficult to investigate. The theoretical average time complexity is O(n^2) and O(nlogn), respectively, for interpolation and fast sorting, where the best case time complexity of interpolation is O(n). It is not difficult to draw a conclusion by comparison that when n is small enough, the advantage of fast platoon becomes smaller. In fact, the sorting performance of small data sets can be better than that of fast sorting.
2. Why sentry
Because the performance bottleneck of quicksort is the depth of the recursion, the worst case scenario is that each sentry is either the smallest or the largest element, so partition (with elements smaller than the sentry on one side and elements larger than the sentry on the other) will leave one side empty. If you do this, the number of recursive levels is n, and each level is O(n), so fast sorting will degenerate to O(n^2).
This situation is to be avoided, so how to avoid? The idea is to keep the sentry element in the middle of the array as much as possible, with as few maxims or minims as possible
Finally, let’s look at the basic structure of sort in the source code
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);
}
function InnerArraySort(array, length, comparefn) {
// The comparison function is not passed in
if(! IS_CALLABLE(comparefn)) { comparefn =function (x, y) {
if (x === y) return 0;
if (%_IsSmi(x) && %_IsSmi(y)) {
return %SmiLexicographicCompare(x, y);
}
x = TO_STRING(x);
y = TO_STRING(y);
if (x == y) return 0;
else return x < y ? -1 : 1;
};
}
function InsertionSort(a, from, to) {
// Insert sort
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 GetThirdIndex(a, from, to) { // Find sentry elements if the number of elements is greater than 1000
var t_array = new InternalArray();
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++;
}
t_array.sort(function(a, b) {
return comparefn(a[1], b[1]);
});
var third_index = t_array[t_array.length >> 1] [0];
return third_index;
}
function QuickSort(a, from, to) { // Quicksort implementation
// Sentry position
var third_index = 0;
while (true) {
if (to - from< =10) {
InsertionSort(a, from, to); // Small data volume, use insert sort, fast
return;
}
if (to - from > 1000) {
third_index = GetThirdIndex(a, from, to);
} else {
// Select the midpoint if the value is less than 1000
third_index = from + ((to - from) > >1);
}
// Start quick sorting
var v0 = a[from];
var v1 = a[to - 1];
var v2 = a[third_index];
var c01 = comparefn(v0, v1);
if (c01 > 0) {
var tmp = v0;
v0 = v1;
v1 = tmp;
}
var c02 = comparefn(v0, v2);
if (c02 >= 0) {
var tmp = v0;
v0 = v2;
v2 = v1;
v1 = tmp;
} else {
var c12 = comparefn(v1, v2);
if (c12 > 0) {
var tmp = v1;
v1 = v2;
v2 = tmp;
}
}
a[from] = v0;
a[to - 1] = v2;
var pivot = v1;
var low_end = from + 1;
var high_start = to - 1;
a[third_index] = a[low_end];
a[low_end] = pivot;
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++; }}}// The core idea of quicksort, recursive call quicksort method
if (to - high_start < low_end - from) {
QuickSort(a, high_start, to);
to = low_end;
} else {
QuickSort(a, from, low_end);
from= high_start; }}}Copy the code