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

The last article looked at sorting methods, and there are more in this series – see the end of this article

In this article, we will continue to learn about sorting methods in JavaScript: sorting algorithms are often used in practical work to count sorting

JavaScript sort algorithm – count sort

The core of counting sort is to convert input data values into keys and store them in extra array space.

As a sort of linear time complexity, counting sort requires that the input data must be integers with a definite range.

function countingSort(arr, maxValue) {
  var bucket = new Array(maxValue + 1),
    sortedIndex = 0; (arrLen = arr.length), (bucketLen = maxValue +1)

  for (var i = 0; i < arrLen; i++) {
    if(! bucket[arr[i]]) { bucket[arr[i]] =0
    }
    bucket[arr[i]]++
  }

  for (var j = 0; j < bucketLen; j++) {
    while (bucket[j] > 0) {
      arr[sortedIndex++] = j
      bucket[j]--
    }
  }

  return arr
}
// Introduce the following method to test the code time:
getFnRunTime(countingSort)
Copy the code

A way to test how long a function’s code takes to run

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

let len = testArr.length
/ * * *@desc Test 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(`total time: ${endTime - startTime}ms, `."test array'length: " + len, result.length)
}
Copy the code
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 code

Read more

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