This is the 18th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

In this article, you will learn how to sort a list by selecting a sort. You will learn how to sort a list by selecting a sort

In this article, we will continue with the classic sorting method: insert sort, which is usually faster than selection sort

JS implementation of sorting algorithm – insertion sort

Insertion sort is one of the most simple and intuitive sorting algorithms. Its working principle is to build an ordered sequence and scan the unsorted data from back to front in the sorted sequence to find the corresponding position and insert it.

Like bubble sort, insert sort also has an optimization algorithm called split insert.

Insert sort algorithm steps

  1. 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.
  2. 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.)

Insert sort JS code implementation:

Insert sort code implementation although not bubble sort and selection sort as simple and crude, but its principle should be the most easy to understand, because as long as the poker should be relatively easy to understand.

  1. Insertion sortinsertionSortfunction
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
}
Insert sort: insert sort: insert sort: insert sort: insert sort
getFnRunTime(insertionSort)
Copy the code

A function that tests the time it takes for code to run

In this case, insertionSort is suitable for sorting data with a small amount of data, so 20W + data is not suitable for..

const testArrFn = function (len) {
  let arr = []
  const count = len
  for (let i = 0; i < count; i++) {
    arr[i] = Math.floor(Math.random() * 50 + 1)}return arr
}
Copy the code

Tools: by testing data (array), method execution time

let testArr = testArrFn(len)

let len = testArr.length
/ * * *@desc Method function execution time */
module.exports = async function getFnRunTime(fn) {
  let startTime = Date.now(),
    endTime
  let result = await fn(testArr)
  endTime = Date.now()
  console.log(testArr, result)
  console.log(, "test_array'length: " + len, result.length,'Sorting time -total time:${endTime - startTime}ms, `)}Copy the code

Read more

  • 】 【 Array. The prototype. The map (),
  • JS- special symbol – bit operator
  • 【ES6 – for/of】,
  • JS- Logical operator – short circuit? ,
  • 【JS- arrow function 】
  • 】 【 JavaScript – forEach (),

Classical sorting algorithm:

  • 【 jS-sort algorithm -sort()】,
  • 【JavaScript- sort algorithm – Hill sort 】
  • 【JS- sorting algorithm – merge sort 】,
  • 【JavaScript- sorting algorithm – counting sort 】
  • 【JS- sort algorithm – bubble sort 】
  • JS- Classical sorting algorithm – selection sort