preface

Recently, in order to consolidate the foundation of their algorithm, and the basic algorithm in the algorithm book brush again, especially to summarize the front-end engineers need to understand the sorting algorithm and search algorithm knowledge, although there are a lot of advanced algorithms need to understand, but the foundation or to consolidate. This article will introduce the following algorithm knowledge in the form of text and text, and I hope you can gain something after reading it:

  • Bubble sort and its optimization
  • Selection sort
  • Insertion sort
  • Merge sort
  • Quick sort
  • Sequential search
  • Binary search

The body of the

I think the biggest headache for every front-end engineer is algorithms, but algorithms are often a very important indicator of a person’s programming ability. At present, many mainstream frameworks and libraries have applied a large number of algorithms and design patterns, in order to make their own higher level, we can only continue to “hit the monster “(that is, brush algorithm) upgrade, to become the” strongest king “.

Actually front-end development over the years, more and more favor of fine development, a lot of super applications (such as taobao, WeChat) are all in the pursuit of perfection of the user experience, time is money, this requires that the engineers can’t as before, the development of the program just can use, we tend to a more detailed test (including unit tests, Performance testing, etc.), for sorting, for large amounts of data, we would be crazy to use bubble sort, because the performance of bubble sort is very poor (complexity O(n^2). In real projects we don’t tend to use bubble sort, we tend to use quicksort or Hill sort. I’m here on the performance of sorting algorithms

  • How to make front-end code 60 times faster

Let’s learn how to implement some of the common sorting and search algorithms used at the beginning of this article.

Bubble sort and its optimization

When we learn sorting algorithms, one of the easiest to master is bubble sort, because it’s very easy to implement, but from a performance standpoint, it’s one of the worst performing.

The idea behind bubble sort is to compare any two adjacent items and swap them if the former is larger than the latter.

In order to show the process and performance test of bubble sort more conveniently, the author first wrote several tool methods, which are the methods of dynamically generating a specified number of random number groups and generating element position sequence respectively. The code is as follows:

// Generate a specified number of random numbers
const generateArr = (num = 10) = > {
  let arr = []
  for(let i = 0; i< num; i++) {
    let item = Math.floor(Math.random() * (num + 1))
    arr.push(item)
  }
  return arr
}

// Generate a specified number of x coordinates for the elements
const generateArrPosX = (n= 10, w = 6, m = 6) = > {
  let pos = []
  for(let i = 0; i< n; i++) {
    let item = (w + m) * i
    pos.push(item)
  }
  return pos
}
Copy the code

With these two methods, we can generate any number of arrays and array entry coordinates, which we will use next.

Let’s write a beggar’s version of bubble sort:

bubbleSort(arr = []) {
    let len = arr.length
    for(let i = 0; i< len; i++) {
      for(let j = 0; j < len - 1; j++) {
        if(arr[j] > arr[j+1]) {
          / / replacement
          [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
        }
      }
    }
    return arr
  }
Copy the code

To test this, we use the generateArr method to generate an array of 60 items and dynamically generate the element coordinates:

// Generate coordinates
const pos = generateArrPosX(60)
// Generate an array of 60 items
const arr = generateArr(60)
Copy the code

After executing the code, the following random node structure is generated:

A deeper look at the code shows that the two-level for loop sorting causes a lot of redundant sorting. If we subtract the number of rounds that have been run in the outer loop from the inner loop, we can avoid unnecessary comparisons in the inner loop, so we optimize the code as follows:

// Bubble sort optimized version
bubbleSort(arr = []) {
  let len = arr.length
  / / optimization
  for(let i = 0; i< len; i++) {
    for(let j = 0; j < len - 1 - i; j++) {
      if(arr[j] > arr[j+1]) {
        / / replacement
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
      }
    }
  }
  return arr
}
Copy the code

The optimized bubble sort takes 0.279052734375ms, slightly better than before, but still not the recommended sort algorithm.

Selection sort

The idea of sorting is to find the minimum value in the data structure and place it first, then find the second minimum and place it second, and so on.

We will generate an array of 60 items as follows:

selectionSort(arr) {
    let len = arr.length,
        indexMin
    for(let i = 0; i< len - 1; i++) {
      indexMin = i
      for(let j = i; j < len; j++){
        if(arr[indexMin] > arr[j]) {
          indexMin = j
        }
      }
      if(i ! == indexMin) { [arr[i], arr[indexMin]] = [arr[indexMin], arr[i]] } }return arr
}
Copy the code

When you click on sort, the result is as follows:

Bubble sort

Insertion sort

The idea of insertion sort is to sort the array one at a time, assuming that the first item is sorted, and then compare it to the second item to determine the position of the second item, and then in the same way determine the position of the third item, and so on, and then sort the entire array from smallest to largest.

The code is as follows:

insertionSort(arr) {
    let len = arr.length,
        j,
        temp;
    for(let i = 1; i< len; i++) {
      j = i
      temp = arr[i]
      while(j > 0 && arr[j- 1] > temp) {
        arr[j] = arr[j- 1] j-- } arr[j] = temp; }}Copy the code

The execution result is as follows:

Merge sort

Merge sort algorithm performance is better than the above three, can be used in real projects, but the implementation is relatively complex.

Merge sort is a dive-and-conquer algorithm, where the idea is to cut the original array into smaller arrays until each one has only one element, then merge the smaller arrays into larger arrays, and finally make a sorted large array.

The implementation process is shown in the figure below:

// Merge sort
mergeSortRec(arr) {
 let len = arr.length
 if(len === 1) {
   return arr
 }
 let mid = Math.floor(len / 2),
     left = arr.slice(0, mid),
     right = arr.slice(mid, len)
 return merge(mergeSortRec(left), mergeSortRec(right))
}
// Merge methods
merge(left, right) {
    let result = [],
        l = 0,
        r = 0;
    while(l < left.length && r < right.length) {
      if(left[l] < right[r]) {
        result.push(left[l++])
      }else {
        result.push(right[r++])
      }
    }
    while(l < left.length) {
      result.push(left[l++])
    }
    while(r < right.length) {
      result.push(right[r++])
    }
    return result
}
Copy the code

The recursion in the above code is to divide a large array into smaller arrays until there is only one item, and then to sort through the merge layer by layer. If you don’t understand, you can communicate with the author or combine the sketches drawn by the author to understand.

Quick sort

Quicksort is currently more commonly used sorting algorithm, its complexity is O(nlog^n), and its performance is better than other complexity is O(nlog^n), is also using the idea of divide and conquer, the original array partition, because quicksort implementation is more complex, here is the idea:

  1. Select the middle item from the array as the pivot
  2. Create two Pointers, one on the left to the first item in the array, one on the right to the last item in the array, move the left pointer until we find an element that is larger than the pivot, move the right pointer until we find an element that is smaller than the pivot, swap them, and repeat the process until the left pointer exceeds the right pointer
  3. The algorithm repeats the steps 1,2 for the partition of the small array until the array is completely sorted.

The code is as follows:

// Quicksort
quickSort(arr, left, right) {
    let index
    if(arr.length > 1) {
      index = partition(arr, left, right)
      if(left < index - 1) {
        quickSort(arr, left, index - 1)}if(index < right) {
        quickSort(arr, index, right)
      }
    } 
  }
// Divide the process
partition(arr, left, right) {
    let part = arr[Math,floor((right + left) / 2)],
        i = left,
        j = right
    while(i <= j) {
      while(arr[i] < part) {
        i++
      }
      while(arr[j] > part) {
        j--
      }
      if(i <= j) {
        / / replacement
        [arr[i], arr[j]] = [arr[j], arr[i]]
        i++
        j--
      }
    }
    return i
}
Copy the code

Sequential search

Search algorithm is also one of the algorithms we often use, for example, we need to find a user or a piece of data, whether it is on the front end or back end, will use search algorithm. Let’s start with the simplest and least efficient sequential search. The main idea is to compare the elements in each data structure to the element we are querying, and then return the index of the specified element.

sequentialSearch(arr, item) {
    for(let i = 0; i< arr.length; i++) {
      if(item === arr[i]) {
        return i
      }
    }
    return - 1
}
Copy the code

Next, let’s look at a more common and flexible search algorithm – binary search.

Binary search

The idea of binary search is a bit like “speculation”, but it is a kind of “speculation” with theoretical basis. First it requires that the data structures being searched be sorted, and then it does the following:

  1. Find the middle value of the array
  2. If the intermediate value is the value to be searched, the index of the intermediate value is returned
  3. If the value to be searched is smaller than the median value, step 1 is returned, narrowing the range and continuing the search in the subarray to the left of the median value
  4. If the value to be searched is larger than the selected value, step 1 is returned to narrow the range and continue searching in the subarray to the right of the middle value
  5. If none is found, -1 is returned

In order to facilitate understanding, the author drew the following sketch:

binarySearch(arr, item) {
    // Call the sorting algorithm to sort the data first
    this.quickSort(arr)

    let min = 0,
        max = arr.length - 1,
        mid,
        el
    while(min <= max) {
      mid = Math.floor((min + max) / 2)
      el = arr[mid]
      if(el < item) {
        min = mid + 1
      }else if(el > item) {
        max = mid - 1
      }else {
        return mid
      }
    }
    return - 1
  }
Copy the code

In fact, there are many search algorithms, the author in JS basic search algorithm implementation and 1.7 million data under the performance test has a specific introduction.

The last

If you want to learn more H5 games, Webpack, node, gulp, CSS3, javascript, nodeJS, Canvas data visualization and other front-end knowledge and practical, welcome to join our technical group in the public number “Interesting Talk front-end” to learn and discuss together, and explore the boundary of the front-end.

More recommended

  • A few very interesting summaries of javascript knowledge points
  • Front-end advanced from zero to one to achieve unidirectional & bidirectional linked list
  • Preliminary study of micro front-end architecture and my front-end technology inventory
  • Browser Cache Library Design Summary (localStorage/indexedDB)
  • Develop your own graph bed application using nodeJs
  • Implementing a CMS full stack project from 0 to 1 based on nodeJS (Part 1)
  • Implement a CMS full stack project from 0 to 1 based on nodeJS (middle) (source included)
  • CMS full stack project Vue and React (part 2)
  • Write a mock data server using nodeJS in 5 minutes
  • Develop a component library based on VUE from zero to one
  • Build a front-end team component system from 0 to 1 (Advanced Advanced Prerequisite)
  • Hand-write 8 common custom hooks in 10 minutes
  • Master Redux: Developing a Task Management platform (1)
  • Javascript Design Patterns front-end Engineers Need to Know in 15 minutes (with detailed mind maps and source code)
  • A picture shows you how to play vue-Cli3 quickly
  • “Front End Combat Summary” using postMessage to achieve pluggable cross-domain chatbot