In recent days in the system review sorting algorithm, before have no systematic study, also did not leave any notes, so soon forget, this time to learn.

First of all, in order to reduce restrictions, the following code runs on the Node V8 engine, not the browser. The source code is on my GitHub. If you are interested, you can download it and run it.

GenerateArray = generateArray; generateArray = generateArray; generateArray = generateArray

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

You only need to input the length of the array to generate a random number set that meets the length requirements.

Bubble sort

Bubble sort is also called a sinking sort. Bubble sort gets its name from the way it traverses the entire array, comparing each item to the next item, and swapping if it doesn’t fit, in a total of n rounds where n is the length of the array. After n rounds, the array is fully sorted. The items that fit the bill bubble to the end of the array like bubbles rising from the bottom to the surface, so it’s called bubble sort.

Bubble sort is the simplest sorting method, easy to understand and implement, but bubble sort is the least efficient sorting algorithm, because the algorithm nested two cycles (traversing the array n times), so the time complexity is O(n^2). In the best case, bubble sort is given to a sorted array in order time order n.

Thank you for the optimization of @xuezhiqi dance in the comments. Every time you bubble, you ignore the I item that has been sorted in the tail.

JavaScript implementation (in descending order) :

function bubbleSort(arr) { //console.time('BubbleSort'); // Get the array length to determine the number of loops. let len = arr.length; // Iterate through the array len times to make sure the array is fully sorted. for(let i=0; i<len; I ++) {// Iterate over the first len-i term of the array, ignoring the next I term (sorted portion). for(let j=0; j<len - 1 - i; J++) {// compare each item with the last one, and swap the ones that don't meet the requirements. if(arr[j] > arr[j+1]) { [arr[j+1], arr[j]] = [arr[j], arr[j+1]]; } } } //console.timeEnd('BubbleSort'); return arr; }Copy the code

The code in the comment section of the code is used to output the sort times for testing purposes, as is the case below.

Second, selection sort

Selection sort is a kind of local comparison sort method.

Find the smallest (largest) value in the array and place it first, then find the second-smallest value and place it second… And so on.

JavaScript implementation (in descending order) :

function selectionSort(arr) { //console.time('SelectionSort'); // Get the array length to make sure that each item is sorted. let len = arr.length; // Iterate over each item of the group. for(let i=0; i<len; I++) {// start with the current item of the array, because the items on the left have already been sorted. let min = i; for(let j=i; j<len; j++) { if(arr[j] < arr[min]) { min = j; } } if(min ! == i) { [arr[min], arr[i]] = [arr[i], arr[min]]; } } //console.timeEnd('SelectionSort'); return arr; }Copy the code

The time complexity is also O(n^2) because of the nested two-layer loop,

Insert sort

Insertion sort is the closest thing to life sort, because that’s pretty much what we do when we play cards. The method from an array of the second group began to iterate through the n – 1 item (n is the length of the array), traversing the paragraphs for the current to the left of the array in the process, comparing in turn from right to left, if the option is greater than or less than the current item on the left, the options on the left to the right, and then continue to contrast before a, until you find no greater than (not less than its own option, For all options larger than the current item, one item is moved to the right from the original position.

Example:

Var arr = [2,1,3,5,4,3]; // a[0] >= 1 is true, a[0] is moved to the right, arr = [2,2,3,5,4,3]; // Then assign 1 to a[0], arr = [1,2,3,5,4,3]; // then the second round: // a[1] >= 3 is not valid, the round traversal ends. // round 3; // a[2] >= 5 does not exist, and the round traversal ends. The fourth round: / / / / a [3] > = 4 to true, a [3] moves to the right, arr =,2,3,5,5,3 [1]; // a[2] >= 4 is not true, assign 4 to A [3], then end the round traversal. ,2,3,4,5,3 arr = [1]; Arr = [1,2,3,4,5,5]; arr = [1,2,3,4,5]; / / arr [3] > = 3, arr [3] moves to the right one, arr =,2,3,4,4,5 [1]; / / arr [2] > = 3, arr [2] moves to the right one, arr =,2,3,3,4,5 [1]; // arr[1] >= 3 does not exist, assign 3 to a[2], end the round. ,2,3,3,4,5 arr = [1]; // The sorting is complete.Copy the code

If we remove the equal sign from the comparison, we can reduce some steps, so we reduce this part in the JavaScript code, and the JavaScript implementation (sort from smallest to largest) :

function insertionSort(arr) {
    //console.time('InsertionSort');
    let len = arr.length;
    for(let i=1; i<len; i++) {
        let j = i;
        let tmp = arr[i];
        while(j > 0 && arr[j-1] > tmp) {
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = tmp;
    }
    //console.timeEnd('InsertionSort');
    return arr;
}
Copy the code

Insertion sort is worse than the general advanced sorting algorithm (fast sorting, heap sorting), but it still has the following advantages:

  • Simple to implement, not very complicated to understand.
  • It’s efficient for smaller data sets.
  • Faster than other sorting algorithms with O(n^2) complexity (bubble, select). This can be seen in the test at the end of the article.
  • Stable, timely…

Merge sort

So far, three sorting methods have been introduced, including bubbling sort, selection sort, and insertion sort. The time complexity of these three sorting methods is O(n^2). Among them, bubble sort is the simplest and has the worst performance. Selection sort is slightly better than bubble sort, but it is not enough. Because of these reasons, the practicability of the three is not high. They are the most basic simple sorting methods, which are mostly used in teaching, but difficult to be used in practice. From this section, more advanced sorting algorithms will be introduced.

Merge sort is the first algorithm that can be used in real sorting. The performance of the first three algorithms is not good enough. The time complexity of merge sort is O(nlogn), which is already due to the first three algorithms.

It’s worth noting that the array.prototype. sort method in JavaScript doesn’t specify which sort algorithm to use and allows the browser to customize it. FireFox uses merge sort, while Chrome uses quicksort.

The core idea of merge sort is divide and conquer. Divide and conquer is an idea that the problem is recursively decomposed into two or more sub-problems of the same or related type until the problem is simple enough to be solved, and then the solutions of the sub-problems are combined to solve the original solution.

Merge sort synthesizes subproblem solutions by breaking complex arrays into sufficiently small arrays (containing only one element) and then combining two ordered arrays (groups of unit prime numbers can be considered ordered arrays). So the core of merge sort is how to combine two ordered arrays, and splitting arrays is just a secondary process.

Example:

Var arr = [8,7,6,5]; var arr = [8,7,6,5]; [8], [7], [6], [5] // Start merging the arrays to get two arrays: [8], [7], [6], [5] [7,8] and [5,6] // continue merging to get [5,6,7,8] // sort completeCopy the code

JavaScript implementation (in descending order) :

function mergeSort(arr) { //console.time('MergeSort'); //let count = 0; console.log(main(arr)); //console.timeEnd('MergeSort'); //return count; // The main function. Function main(arr) {function main(arr) {// Remember to add judgment, prevent infinite recursion caused by the callstack overflow, also is the end of the array decomposition condition. if(arr.length === 1) return arr; // Start from the middle and construct the left and right arrays. let mid = Math.floor(arr.length/2); let left = arr.slice(0, mid); let right = arr.slice(mid); // Start the recursive call. return merge(arguments.callee(left), arguments.callee(right)); } // Left is the left ordered array, right is the right ordered array. Function merge(left, right) {// il is a pointer to the left array, rl is a pointer to the right array. let il = 0, rl = 0, result = []; // Iterate over the left and right arrays until one pointer is out of range. while(il < left.length && rl < right.length) { //count++; If the current item of the left array is less than the current item of the right array, push the current item of the left array to result and vice versa, and move the pushed pointer to the right. if(left[il] < right[rl]) { result.push(left[il++]); } else { result.push(right[rl++]); }} // Remember to read the excess of the unread array to result. return result.concat(left.slice(il)).concat(right.slice(rl)); }}Copy the code

Note that because arrays are split into many subarrays with only one element, the merge function merges an array with only one element. When the number of elements in the merged array exceeds 1, it is an ordered array. You can still use the merge function to merge arrays.

The performance of merge sort is application-level, but it is not enough because the merge function creates a new result array to hold the merged array, which increases space complexity. You can also optimize the merge function to make the array sort in place.

Quicksort

Quicksort, invented by Tony Hoare in 1959, is the most commonly used sorting scheme. If used properly, it can be two or three times faster than ordinary algorithms, and tens of thousands of times faster than bubble sort, selection sort and so on. Quicksort is O(nlogn), and the core idea is divide-and-conquer, which is to recursively decompose a large array into a small array of length one, but it differs from merge sort in that it focuses on array decomposition, whereas merge sort focuses on array merging.

Basic idea:

Pick a reference point in the array (Pivot), and for each item in the array, place everything larger than pivot to the right and everything smaller than pivot to the left. The left and right elements form two new arrays (left and right), then continue to decompose the left and right. Until the length of the array is 1, and then the array is merged.

Basic steps:

  • (1) First, choose the middle item of the array as the reference point pivot.
  • (2) Create two Pointers left and right, with the left pointing to the first item and the right pointing to the last item, and move the left pointer until its value is no less than pivot, and then move the right pointer until its value is no more than Pivot.
  • (3) If left is still not greater than right, swap the left and right Pointers (Pointers do not swap), then move left to right and right to left, continue the loop until left is greater than right, and return the left pointer value.
  • (4) According to the result of the last round of decomposition (left value), cut the array to get left and right two arrays, and then decompose them respectively.
  • (5) Repeat the above process until the array length is 1.

JavaScript implementation (in descending order) :

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) {// Condition that the recursion ends until the array contains only one element. If (arr. Length === 1) {// If (arr. Length === 1) { return; } // get the left pointer for the next round of decomposition. let index = partition(arr, left, right); If (left < index - 1) {// Continue to decompose the left array. main(arr, left, index - 1); } if(index < right) {// Decompose the right array. main(arr, index, right); }} // Array decomposition function. Function partition(arr, left, right) {// Select the middle item as the reference point. let pivot = arr[Math.floor((left + right) / 2)]; // loop until left > right. While (left <= right) {// Keep moving the left pointer right until its value is not less than pivot. while(arr[left] < pivot) { left++; } // Keep moving the right pointer left until its value is no greater than pivot. while(arr[right] > pivot) { right--; } // The value of the left pointer is not less than pivot, and the value of the right pointer is not greater than pivot. // If left is not greater than right. If (left <= right) {// Swap the values of the two so that the value not greater than pivot is to its left and the value not less than pivot is to its right. [arr[left], arr[right]] = [arr[right], arr[left]]; // The left pointer moves right, the right pointer moves left ready to start the next turn, preventing arR [left] and ARR [right] from both being equal to pivot and then causing an infinite loop. left++; right--; }} // Returns the left pointer as the basis for the next round of decomposition. return left; }}Copy the code

Compared with merge sort, quicksort strengthens the logic of decomposition part, eliminates the work of array merge, and does not allocate new memory to store the result of array merge, so the performance is better, is the most commonly used sort scheme at present.

I also saw an answer on Zhihu before, and the code is roughly as follows (in descending order) :

Function quickSort(arr) {// If the array length is less than 1, return the result to prevent callStack overflow. if(arr.length <= 1) return arr; Return [// Recursively calls quickSort, using array.prototype. filter to filter values less than arr[0], QuickSort (arr.slice(1).filter(item => item < arr[0])), arr[0], ...quickSort(arr.slice(1).filter(item => item >= arr[0])) ]; }Copy the code

The above code is conducive to the understanding of the idea of fast sorting, but the actual application effect is not good, not as fast as the previous code.

Heap sort

If quicksort is the most versatile sort algorithm, then I think heapsort is the most interesting sort algorithm, very interesting.

Heap sort is also a very efficient sorting method, because it takes the array as a binary tree sorting named, can be regarded as an improved scheme of merge sort, it is an in-place sorting method, but not stable, its time complexity is O(nlogn).

Implementation steps:

  • (1) Construct a heap structure from arrays such that the parent node is always greater than (or less than) its children.
  • (2) Starting from the rightmost leaf node of the heap structure, exchange with the root node from right to left and from bottom to top. After each exchange, the heap structure should be constructed again. It is important to note that each time the heap structure is built, non-root nodes that have been swapped are ignored.

Array build heap structure:

Var arr = [1,2,3,4,5,6,7]; // Heap structure 1 / \ 23 / \ / \ 4 5 6 7Copy the code

It can be found that for an array item with subscript I, the value of the left child is the item with subscript 2* I + 1, and the value of the right child is the item with subscript 2* I + 2.

There is no actual space in memory to build a heap structure to store the array data, but the array is logically treated like a binary tree, and the heap structure means that no child of any parent node is larger than (or less than) the parent node.

JavaScript implementation (in descending order) :

function heapSort(arr) { //console.time('HeapSort'); buildHeap(arr); for(let i=arr.length-1; i>0; I --) {// Start with the rightmost leaf node and swap with the root node. [arr[i], arr[0]] = [arr[0], arr[i]]; // After each exchange, the heap structure is rebuilt. Remember to pass in the I limit to prevent the swapped values from still being rebuilt. heapify(arr, i, 0); } //console.timeEnd('HeapSort'); return arr; Function buildHeap(arr) {// See that the middle subscript corresponds to the parent of the rightmost leaf node. let mid = Math.floor(arr.length / 2); for(let i=mid; i>=0; I --) {// Build the entire array into a heap structure for initialization. heapify(arr, arr.length, i); } return arr; } // Subscript the function that builds the heap structure in heapSize, starting at the I node. Function heapify(arr, heapSize, I) {// left child subscript. Let left = 2 * I + 1, // right child subscript Right = 2 * I + 2, // Assuming the current parent node meets the requirements (larger than the child nodes). largest = i; // If the left child is in heapSize and has a value greater than its parent, then left is assigned to largest. if(left < heapSize && arr[left] > arr[largest]) { largest = left; } // If the right child is in heapSize and has a value greater than its parent, then right is assigned to largest. if(right < heapSize && arr[right] > arr[largest]) { largest = right; } if(largest ! == I) {// If largest is modified, then swap the two values to construct a qualified heap structure. [arr[largest], arr[i]] = [arr[i], arr[largest]]; // Recursively calls itself to build heaps of all the children of node I. arguments.callee(arr, heapSize, largest); } return arr; }}Copy the code

Heap sort doesn’t perform as well as quicksort, but it’s really fun.

Seven, performance comparison

Using console.time() and console.timeend () to look at the time taken for sorting, generateArray() to generate a large amount of data, and finally get the following conclusion:

Through the bubble sorting test, the following data are obtained:

The BubbleSort: 406.567 msCopy the code

Sorting 10,000 (ten thousand) pieces of data takes 406 milliseconds.

The BubbleSort: 1665.196 msCopy the code

It takes 1.6 seconds to sort 20,000 (20,000) pieces of data.

The BubbleSort: 18946.897 msCopy the code

Sorting 50,000 (50,000) pieces of data takes 19 seconds. Because the machine is not very good, when the data volume reaches 100000, it is basically very long, and the specific time has not been waited, which already shows that the performance is very poor.

By testing the selection sort, the following data are obtained:

SelectionSort: 1917.083 msCopy the code

It takes 1.9 seconds to sort 20,000 (20,000) pieces of data.

SelectionSort: 12233.060 msCopy the code

Sorting 50,000 (50,000) pieces of data takes 12.2 seconds, which is an improvement over bubble sorting, but not nearly enough. It can also be seen that as the amount of data increases, the time consumption of sorting becomes larger and larger.

Through the test of insertion sort, the following data is obtained:

InsertionSort: 273.891 msCopy the code

It takes 0.27s to sort 20,000 (20,000) pieces of data.

InsertionSort: 1500.631 msCopy the code

Sorting 50,000 (50,000) pieces of data takes 1.5 seconds.

InsertionSort: 7467.029 msCopy the code

Sorting 100,000 (100,000) pieces of data takes 7.5 seconds, again a big improvement over selection sorting, but still not enough.

Through the test of merge sort, the following data are obtained:

MergeSort: 287.361 msCopy the code

Sort 100,000 (100,000) pieces of data in 0.3 seconds. Pretty good.

MergeSort: 2354.007 msCopy the code

Sorting 1,000,000 (one million) pieces of data takes 2.4 seconds, which is pretty good, so no wonder FireFox uses this to define array.prototype. sort,

MergeSort: 26220.459 msCopy the code

Sorting 10 million (10 million) pieces of data takes 26 seconds, not bad. Now let’s look at quickrow.

Through the test of quicksort, the following data are obtained:

QuickSort: 51.446 msCopy the code

It takes 0.05s to sort 100000 (100,000) pieces of data, reaching the level of negligible.

QuickSort: 463.528 msCopy the code

It takes 0.46 seconds to sort 1,000,000 (one million) pieces of data, which is negligible.

QuickSort: 5181.508 msCopy the code

Sorting 10000000 (10 million) data takes 5.2s, which is totally acceptable.

Through the heap sort test, we get the following data:

HeapSort: 3124.188 msCopy the code

Sorting 1,000,000 (one million) items of data takes 3.1 seconds, not as fast as quicksort and merge sort, but still pretty good compared to other sorting methods.

HeapSort: 41746.788 msCopy the code

Sorting 10,000,000 (10 million) pieces of data takes 41.7s, which is not acceptable.

Eight, the conclusion

I used to think that sorting methods can be used freely, but now I think it is quite naive HHH, thinking of the previous internship, SQL Server millions of data sorting completed in a few seconds, this if you use bubble sorting also have to wait until two eyes black? Through this learning summary sorting algorithm, especially for each method performance test, I deeply realized the importance of algorithm design, only pay attention to the design of the algorithm, complexity contrast, to write excellent algorithm, based on excellent algorithm to write excellent performance application!

In addition, due to the lack of in-depth research on algorithm complexity, the understanding is only superficial, so if there are any mistakes in the paper, please kindly comment!

Finally, I want to say, support Teacher Ruan!

9. Refer to the article

  • Bubble sort
  • Selection sort
  • Insertion sort
  • Merge sort
  • Quicksort
  • Heapsort
  • Sorting algorithm
  • Algorithm complexity analysis
  • Learning javascript Data Structures and Algorithms (2nd edition)