Author: Yiyun
Reading to tail link: http://blog.cdswyda.com/post/javascript/2017-03-22-js-sort-not-only-bubblesort (click)
Has been authorized to reprint
It is highly recommended that you read a book on gitBook – Ten classic sorting algorithms: https://sort.hust.cc/, the GIF and demo code of this article are here.
Sorting is a necessary requirement in programming. The front end is no exception. It’s rare, but you’ll definitely run into it.
But when it comes to sorting, the easiest thing to think about is bubble sort, select sort, insert sort.
Bubble sort
Compare two adjacent elements in turn, and if the latter is less than the previous, swap, so that the largest element is placed at the end of the first one.
Let’s do it again from start to finish, and since the last one is already the largest for each round, the next round can have one fewer comparisons than the last one. You can still make comparisons from start to finish, but those comparisons are pointless and should be optimized for efficiency.
The picture is shown below:
Code implementation:
function bubbleSort(arr) { var len = arr.length; for (var i = 0; i < len - 1; i++) { for (var j = 0; j < len - 1 - i; J++) {if (arr [j] > arr [j + 1]) {/ / two adjacent element contrast var temp = arr [j + 1); // Element Exchange ArR [J]; arr[j] = temp; } } } return arr; }Copy the codeSelection sort
Choose sort I think is the most simple, freshman VB, just remember the sorting method, the principle is very simple: every time to find a maximum or minimum row at the beginning.
First find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence
Find the smallest (largest) element from the remaining unsorted elements and place it at the end of the sorted sequence.
Repeat the second step until all elements are sorted.
GIF demo:
Code demo:
function selectionSort(arr) { var len = arr.length; var minIndex, temp; for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; J ++) {if (arr[j] < arr[minIndex]) {// find minIndex = j; }} temp = arr[I]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; }Copy the codeInsertion sort
Insertion sort is also relatively easy. Just like poker, you insert the elements in the right place.
Treat the first element of the first to be sorted sequence as an ordered sequence and the second element to the last element as an unsorted sequence.
Scan the unordered sequence from beginning to end, inserting each scanned element into the appropriate place in the ordered sequence. (If the element to be inserted is equal to an element in the ordered sequence, the element to be inserted is inserted after the equal element.)
GIF demo:
Code examples:
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}Copy the codeThe price of simplicity is inefficiency
The above three kinds of sorting methods are very simple, simple at the same time, it will be relatively inefficient, or take this book comparison diagram to illustrate:
They’re all O(n^2), and the sorting algorithms that follow them are all O(n log n).
My OCD is back, and I want a more efficient way of sorting.
Merge sort
I went through the book very briefly, and I understood merge sort at the time, so I’m going to talk a little bit about merge sort.
The basic principle is divide-and-conquer, which is to divide and recursively sort.
The steps are as follows:
Apply for a space equal to the sum of two sorted sequences, which is used to store the combined sequence;
Set two Pointers, starting at the start of two sorted sequences;
Compare the elements pointed to by the two Pointers, select the smaller element into the merge space, and move the pointer to the next position;
Repeat step 3 until a pointer reaches the end of the sequence;
Copies all remaining elements of the other sequence directly to the end of the merged sequence.
GIF demo:
Code examples:
Var mergeSort(arr) {function mergeSort(arr) {var mergeSort(arr); if(len < 2) { return arr; } var middle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right)); } function merge(left, right) { var result = []; while (left.length && right.length) { if (left[0] <= right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } } while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); return result; }Copy the codeSince a person who loves to toss, toss must see the effect.
The efficiency test
And since I learned to sort this, it’s not just an array, it’s an array of objects, you sort some property of an object, and you have to think about descending order.
So my code implementation looks like this:
/** * [merge sort] * @param {[Array]} arr [Array to sort] * @param {[String]} prop * @param {[String]} order [sort mode omitted or asC is ascending otherwise descending] * @return {[Array]} [sorted Array, new Array, Var mergeSort = (function() {var mergeSort = function(left, right, prop) {var result = []; If (prop) {while (left.length && right.length) {if (left[0][prop] <= right[0][prop]) { result.push(left.shift()); } else { result.push(right.shift()); While (left.length && right.length) {if (left[0] <= right[0]) {result.push(left.shift()); } else { result.push(right.shift()); } } } while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); return result; }; Var _mergeSort = function(arr, prop) {var len = arr.length; if (len < 2) { return arr; } var middle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle); return _merge(_mergeSort(left, prop), _mergeSort(right, prop), prop); }; return function(arr, prop, order) { var result = _mergeSort(arr, prop); if (! The order | | order. ToLowerCase () = = = 'asc') {/ / ascending return result; } else {// descending var _ = []; result.forEach(function(item) { _.unshift(item); }); return _; }}; }) ();Copy the codeWhich attributes need to be sorted is uncertain and can be specified at will, so it is written as parameters. Because I don’t want these things to judge each time through the loop, the code is a little redundant.
As for the problem of descending order, there is no parameter added, but a simple ascending order and then reverse output. The reason is I don’t want to have to judge the condition every time I go through the recursion, so I’ll just do it.
Here’s where the efficiency kicks in, in a numerical simulation:
Var getData = function () {return the Mock the Mock ({| 1000 "list" : [{name: '@ cname, age:' @ integer (0500) '}]}). The list; };Copy the codeMock data was simulated using Mock above, about Mock: http://mockjs.com/
Here comes the actual test:
Var arr = getData(); Console. time(' merge sort '); mergeSort(arr, 'age'); Console. timeEnd(' merge sort '); Console. time(' bubble sort '); for (var i = 0, l = arr.length; i < l - 1; ++i) { var temp; for (var j = 0; j < l - i - 1; ++j) { if (arr[j].age > arr[j + 1].age) { temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; }} console.timeEnd(' bubble sort ');Copy the codeFive times, the results are as follows:
// merge sort: 6.592ms
// Bubble sort: 25.959ms
// merge sort: 1.334ms
// Bubble sort: 20.078ms
// merge sort: 1.085ms
// Bubble sort: 16.420ms
// merge sort: 1.200ms
// Bubble sort: 16.574ms
// merge sort: 2.593ms
// Bubble sort: 12.653msCopy the code
The difference between the lowest 4 times and the highest nearly 16 times is satisfactory.
Although 1000 pieces of data makes front-end sorting unlikely, dozens or hundreds of pieces are still possible. And since Node and JavaScript can also run on the server side, this efficiency boost will come in handy.
A little doubt
Merge sort uses recursion. In “JavaScript Description of Data Structures and Algorithms”, the author gives a bottom-up iterative method. But for recursion, the author thinks:
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
However, this approach is not feasible in JavaScript because the recursive depth of the algorithm is too deep for it.
The author of this book on Gitbook has questions about it, and I have questions about it.
It’s a recursive merge, but it’s put after return. The recursion after Renturn is tail-recursion optimization.
Tail-recursive optimization refers to: if a function is called inside the outer function, the outer function needs to wait for the return of the inner function before returning the result. After entering the inner function, the information of the outer function must be remembered in memory, namely the call stack. If the inner function is placed after the return keyword, it means that the outer function is finished. After entering the inner function, it is not necessary to remember all the information in the outer function.
The above is my understanding of the description, I do not know whether it is accurate. Chrome can already enable tail recursion optimization function, I think this recursion should not affect its use in JavaScript.
The last
If you’re interested, I recommend reading this book and thinking about some more efficient ways to sort.
It should be noted, however, that these efficient sorting methods generally require a relatively large amount of additional memory space, which needs to be weighed.
In addition, very small data is not necessary. One is that the impact is too small, but the efficiency of our people, one minute can write from scratch a bubble, select, insert sort method, and change is merge sort?
Tip: Go back to search “sort” and “algorithm” for more related articles.
● This article is numbered 398. If you want to read this article in the future, enter 398 directly.
● Type m to get the article table of contents
Recommend left left left
Algorithms and data structures
More recommendations: 15 Technical Public wechat
Topics: Programlife, Algorithms and Data Structures, Hacker technology and Network security, Big data technology, front-end development, Java, Python, Web development, Android development, iOS development, C/C++,.NET, Linux, database, operation and maintenance, etc.