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

Preface:

In the previous series of articles, we have made a concrete study of JavaScript implementation classical algorithm, summary more reading -list & classical sorting algorithm -list

Then the next some of the other algorithm skills continue to learn record: such as single/double/triple fast row, collision Pointers, and so on

Array sort – three way fast sort

Ideas:

Three-way quicksort divides the entire array into three parts by colliding two Pointers, that is, sorting the three cases of less than the selected value, equal to the selected value, and greater than the selected value simultaneously by double-pointers.

Select a value v at random as the cutoff point, and sort the values less than v, equal to v, and greater than v only once. One pointer is used to carry 1 and one pointer is used to carry 2

Problem solved

Three-way fast sorting is also used to solve the problem of a large number of repeating elements in a sequence, which is more efficient than two-way fast sorting

Divide the array into three parts, less than Pivot, equal to Pivot, and greater than Pivot

The part equal to pivot is not recursive, which greatly reduces the size of the recursive data when sorting arrays with a large number of repeating elements

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)
  • Learn the classic sort algorithm -JS to implement quickSort