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

In the last article, we learned how to sort by bucket. We learned how to sort by bucket. We learned how to sort by bucket

QuickSort is a fast sorting algorithm that can be used to sort objects by buckets and counts.

JS sort algorithm – quick sort

Quicksort, as its name suggests, is a fast sort algorithm. It’s just fast and efficient! It’s one of the fastest sorting algorithms for big data.

Quicksort uses a Divide and conquer strategy to Divide one serial (list) into two sub-lists. Quicksort is generally significantly faster than other two algorithms (NLOGN) because its inner loop can be implemented efficiently on most architectures.

Quicksort is a typical application of divide-and-conquer in sorting algorithm. Quicksort is essentially a recursive divide-and-conquer method based on bubble sort.

Quicksort is simply named. Although Worst Case is O(n²), in most cases it performs better than O(n logn). Why? Explanation in Algorithmic Art and Informatics Contest:

The worst case for quicksort is O(n ^ 2), for example, quicksort. But its amortized expected time is O(nlogn), and the constant factor implied in O(nlogn) notation is very small, much smaller than the stable complexity is O(nlogn) merge sort. Therefore, for most random sequences with weak order, quicksort is always better than merge sort.

Quicksort algorithm steps:

  1. Pick an element from the sequence, called pivot
  2. Reorder the array so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition exits, the benchmark is in the middle of the array. This is called a partition operation;
  3. Recursively sorts subsequences of elements less than the base value and subsequences of elements greater than the base value;

The bottom case of recursion is if the sequence is of size zero or one, so it’s always sorted. The algorithm always exits, though recursively, because in each iteration it puts at least one element in its last position.

Quick sort JavaScript code implementation:

function partition(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

function quickSort(arr, low, high) {
  if (low < high) {
    let pivot = partition(arr, low, high);
    quickSort(arr, low, pivot - 1);
    quickSort(arr, pivot + 1, high);
  }
  return arr;
}
Copy the code

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

The method functions used to create arrays:

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
// Test quicksort to process 20000+ data sort time:
getFnRunTime(quickSort)
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,
  • 【JS implementation – classical sorting algorithm – insert sort 】
  • JS implementation – classical sorting algorithm -JS implementation of radixSort (radixSort)