Data Structure and Algorithm of front-end Science (8) : Implementation and application of Trie tree, the artifact of word prefix matching

preface

The chapter on data structures is over for the time being, and you can start your algorithmic journey here. First from sorting, sorting as the most basic algorithm, is not simple, write a quick row, heap row, merge sort in the interview is not rare, or some questions need to use some sorting ideas to solve, that is why to learn sorting. Of course, the most important thing is to learn its ideas, such as the partition operation of quick sorting, the divide-and-conquer idea of quick sorting and merge sorting, and the performance optimization of sorting, or O(n²) sorting is not useless, etc. In this chapter, we will write down five common sorting algorithms, including bubble sort, selection sort, insertion sort, merge sort, quicksort, and heap sort (described in Chapter 7), understanding their advantages and disadvantages so that we can use the right sort algorithm in the right scenario.

How do you measure a sorting algorithm?

There are many kinds of sorting algorithms. Without understanding the sorting, I naively thought that one of the fastest ones would be chosen directly. But the real picture is a little more complicated, because a ranking can be measured in terms of convenience, not simply efficiency.

1. Time complexity

This is the most intuitive feeling to measure a sorting algorithm. We usually say that the complexity of a certain sort is also the average time complexity, but for different sorting data, there will be the worst time complexity, the best time complexity, so we need to understand what the case is what complexity. Another operation that is often used in sorting is swapping positions and assigning values. Obviously, assignment is more efficient than swapping positions, which also needs to be considered in addition to complexity.

2. Extra memory

To complete the sorting algorithm, how much additional auxiliary space needs to be opened up, that is to say, whether the original array can be directly sorted in situ, this is also a factor to be measured, after all, fast and economical is the meaning of the existence of data structure and algorithm.

Stability of 3.

Although the sorting algorithm is always sorted in ascending or sorting order, it is also a standard to measure whether the position of the same value changes after sorting. For example, [3, 1(1), 2, 1(2)] are all sorted by [1, 1, 2, 3], but it is also important whether the positions of 1 and 2 have changed after sorting. Because in a real world scenario, we might be sorting on a key of an object, and if they have the same key, a stable sorting algorithm will keep the original order unchanged.

bubbleSort

I believe you hear the most is bubble sort, its implementation and principle is really the best to understand. Again, to illustrate the principle of bubble sort:

Compare two adjacent elements, compare their priorities, swap the larger element with the smaller one, and after one round of comparison, the largest element appears at the end of the array, and then the next round excludes the last element (sorted). The process of floating out the highest priority elements is like bubbling. The code is as follows:

const bubbleSort = arr => { for (let i = 0; i < arr.length - 1; For (let j = 0; let j = 0; j < arr.length - i - 1; J++) {/ / - to prevent an array if I narrow range - 1 (arr [j] > arr [j + 1]) {/ / adjacent to compare [arr [j], arr [m + 1]] = [arr [j + 1], arr [j]] / / swap}}}}Copy the code

In this case, we can add a flag to indicate whether the array is sorted or not. If the array is sorted, we can add a flag to indicate whether the array is sorted.

const bubbleSort = arr => { for (let i = 0; i < arr.length - 1; I++) {let flag = true for (let j = 0; j < arr.length - i - 1; J++) {if (arr [j] > arr [j + 1]) {[arr [j], arr [m + 1]] = [arr [j + 1], arr [j]] flag = false / / as long as there is an adjacent exchange, If (flag) {// If (flag) {break}}}Copy the code

Disadvantages of bubble sort

  1. The time complexity is highO (n squared)Two rounds of comparison.
  2. The operation of switching positions is too frequentcpuExecution efficiency.

Advantages of bubble sort

  1. It’s a stable sorting algorithm because it doesn’t swap when the values are equal.
  2. Sort in place without creating extra space.
  3. In the best case, if the array is already sorted, the complexity can be reducedO(n).

selectSort

The principle of implementation is to find the smallest value in the unsorted range, and then swap with the range header element to complete the sorting of the entire array. The principle is shown in the figure below:

First, the head is temporarily stored as min, and then the subscript replacement min of the real minimum value is found in the remaining range. After the inner loop is finished, a swap can be performed. The code is as follows:

selectSort = arr => { for (let i = 0; i < arr.length; I ++) {let min = I // let j = I + 1; j < arr.length; J++) {if (arr/min > arr [j]) {/ / find the smallest min = j}} [arr [I], arr [min]] = [arr (min), arr [I]] / / end of the inner loop exchange}}Copy the code

Also is O (n squared) algorithm, but in terms of execution efficiency, selection sort is better than that of bubble sort, because bubble sort comparison will be exchanged after the operation, the selection is not so, each inner loop is to find the minimum that the subscript, exchange after the inner loop and an array of the head, remain so for the rest of the scope, Therefore, although the number of comparisons is not less, the number of operations to swap positions is much less, and the execution efficiency is higher than bubbling. Again, to illustrate how it works:

Disadvantages of selection sort

  1. The time complexity is high.
  2. It is not a stable sorting algorithm because it switches places every time it finds the smallest value.
  3. The worst and the bestO (n squared)The complexity of.

Advantages of selection sort

  1. Is a kind of in place sorting algorithm, compared with bubble sorting, the operation of switching positions is changed to assignment operation, the execution efficiency will be improved.

insertSort

Its implementation principle is also to divide the array into sorted and unsorted ranges. Each time, the elements are removed from the unsorted range and inserted into the sorted range. The process is repeated to complete the sorting of the entire array. The principle is as follows:

Insertion sort differs from the previous two in that its inner loop is decremented, swapping places with the element before it as long as it is greater than the current one. As you can see from step 4, if it is already sorted, the inner loop can be terminated. The code is as follows:

const insertSort = arr => { for (let i = 1; i < arr.length; I ++) {// = 1 for (let j = I; j > 0; J -) {/ / from I began to decline the if (arr [j] < arr [1]) {before / / if the element is greater than the current [arr [j], arr [1]] = [arr [1], Arr [j]] // switch their positions on} else {break // otherwise end this loop}}}}Copy the code

Because the sorting principle is to look backwards, find the position it should be in, and then insert it into that place, so we can completely switch the position operation to the assignment operation, can have such an optimization, as shown in the following figure:

First of all, the element to be sorted is temporarily saved. Compare the temporary element with the current element to find the position that can be inserted. If the position is not correct, the whole element is moved backwards by the way of assignment. The code is as follows:

const insertSort = arr => { for (let i = 1; i < arr.length; I ++) {let temp = arr[I]; j > 0 && temp < arr[j - 1]; J --) {arr[j] = arr[j-1] // arr[j] = tempCopy the code

Disadvantages of insert sort

  1. The time complexity is high.

Advantages of insertion sort

  1. There are cases of premature loop termination, which is extremely efficient if you’re dealing with an almost ordered array.
  2. In situ sorting does not take up extra space, and the operation without switching positions is highly efficient.
  3. It’s a stable sorting algorithm.
  4. B: At bestO(n).(Sling bubble sort).

mergeSort

Merge sort uses the divide-and-conquer idea of the algorithm, which is to decompose a big problem into a small problem. When the problem is decomposed to a small enough size, the small problem is solved, and the big problem is easily solved.

You divide an array in half, you sort two smaller arrays, and then you divide two smaller arrays into smaller arrays, if you can still split them. Decompose until you have a single element, then merge the group of element primes into an ordered small array, and then merge the two ordered small arrays into a larger array. Until finally, the two arrays that were split into two are all ordered, and they are merged to complete the final sort. The macroscopic principle diagram is as follows:

Then, from the microscopic point of view, how to merge two ordered arrays is shown in the figure below. When merging two ordered arrays, we need to use A copy of the original array to split them into A and B. This is done by reassigning the result of the merge to the original array C.

There are three fixed boundary coordinates which are left/mid/right; And the three moving coordinates k/ I /j. From I to mid is the subarray A, and from mid +1 to right is the subarray B. The merging process only needs to compare the values of the two subarrays respectively. The one whose value is smaller is assigned to the position of the subscript of the original array K, and then move the coordinate +1.

Four things happen during merging:

  1. A[i] > B[j]

We simply assign the value of B[j] to C[k], j++ and k++ to continue merging the next element.

  1. A[i] < B[j]

Assign A[I] to C[k], I ++, and k++ to continue merging the next element.

  1. i > mid

All elements in array A have been merged. You only need to assign the remaining elements in array B to array C. Because these are ordered arrays, everything that’s left in array B is bigger than array A.

  1. j > right

So let’s say we’re all done merging in array B, and we’re going to assign all the remaining values of array A to array C.

The code is as follows:

const mergeSort = arr => { const _mergeSort = (arr, l, (r) = > {if l > = r) {/ / recursive termination conditions return} const mid = l + (r - l) / 2 | 0 / / middle subscript, Mergesort (ARR, L, mid) _mergeSort(ARR, MID + 1, R) _mergeSort(ARr, L, mid, R)} _mergeSort(ARr, 0, Arr. Length - 1)} function _merge(arr, l, mid, r) {const aux = arr. Slice (l, r + 1); let j = mid + 1; for (let k = l; k <= r; K ++) {if (I > mid) {// if arr[k] = aux[j-l] j++} else if (j > r) {// if arr[k] = aux[i-l] I ++} else If (aux[j-l] >= aux[i-l]) {arr[k] = aux[i-l]; I++} else {arr[k] = aux[j-l] j++}}Copy the code

Disadvantages of merge sort

  1. Instead of sorting in place, you need to open up extraO(n)Space.

The advantages of merge sort

  1. There is no best and worst time complexity, in any caseO(nlogn);
  2. It’s a stable sorting algorithm.

5. QuickSort

The star of the sorting algorithm, the time complexity is also true, the fastest of all O(nlogn) sorting, such as JavaScript wrapped by the sort method is using the idea of fast sorting.

The idea of partition is to divide the array into two parts with one element as the partition point, so that all the values of the left array are smaller than the partition point, and all the values of the right array are larger than the partition point. This operation is also called partition. For small arrays that have been partitioned, continue to use the patition operation until they are partitioned into individual elements and cannot be partitioned again. The sorting task of the entire array is complete. Again, to illustrate:

Again, there are two fixed boundary coordinates left and right, and there are two wandering coordinates I and j, where I is the point that we’re going to traverse, and J is the end of the cell, so j plus 1 is the beginning of the larger interval. Suppose we choose the first item of the array as the partition point, then we start with the second item of the array and compare all the remaining items to the partition point. When the point I points to is smaller than the partition point, it is switched with the position j+ 1, j++ extends the range between cells, otherwise the next one is traversed. When the array is completely iterated, the partition is completed by switching the left and j subscripts. The code is as follows:

const quickSort = arr => { const _quickSort = (arr, l, R) => {if (l >= r) {const p = _partition(arr, l, r) _quickSort(arr, p + 1, r)} _quickSort(arr, 0, Arr. Length - 1)} function _partition(arr, l, r) {const v = arr[l] let j = l for (let I = l + 1; i <= r; I++) {// from l + 1, If (v > arr[I]) {// If (v > arr[I]) {// If (v > arr[I]) {// If (v > arr[I]) {// If (v > arr[I]) {// If (v > arr[I]) {// If (v > arr[I]) {// If (v > arr[I]); Function swap (arr, I, j) {[arr[I], arr[j]] = [arr[j], arr[I]]} function swap (arr, I, j) {[arr[I], arr[I]] = [arr[j], arr[I]]}Copy the code

At this point, one of the simplest fast sorting algorithm is implemented. There is much to talk about the star algorithm of fast sorting. In the next chapter, a whole chapter will be devoted to understanding the idea of this kind of sorting algorithm and its optimization.

Disadvantages of quicksort

  1. It’s not a stable sorting algorithm.
  2. The selection of partition points is exquisite, and the worst case will degenerate intoO (n squared).
  3. You need to read the array to be sorted into memory all at once.

Advantages of quicksort

  1. Speed is fast.
  2. Sort in place, just occupyO(logn)Stack space.

The last

At this point, the most commonly used several sorting algorithms are introduced. Sorting algorithms are the building blocks of algorithms, and the next chapter will cover quicksorting alone.

This chapter github source code

Data structures and Algorithms (10) : In-depth understanding of quicksort