Sorting algorithm introduction (JavaScript)

The introduction of

Converts an unordered column of data to an ordered state. Such as:

Numerical order: 5,8,12,23,30,56,68,…..

Dictionary order: an, boy, cow, yellow,…..

classification

Classification by complexity

O(n^2):

1. Insertion sort
2. Comparison sort
3. Bubble sort

O(nlgn):

1. Merge sort
2. Quick sort
3. Block sorting

O (n), O (nk) :

1. Bucket sort
2. Radix sort

Comparison/Others

Based on comparison:

1. Insertion sort
2. Comparison sort
3. Bubble sort
4. Merge sort
5. Quick sort
6. Block sorting

Other:

1. Bucket sort
2. Radix sort

According to whether to open up a new space classification

In place (do not open up memory space in place swap) :

1. Insertion sort
2. Comparison sort
3. Bubble sort
4. Quick sort

The place:

1. Merge sort
2. Bucket sort
3. Block sorting
4. Radix sort

implementation

Binary search

Imagine: If you are a teacher, in a pile of papers, you want to find a certain paper, how would you do, in order to find it in the shortest time.

abstract

   function bsearch(A, x)

    AAn array of:x: Returns the value to be found:x 在 AIn, there is no return -1Copy the code

Cyclic invariant

Before the loop: L: left edge of the search range r: right edge of the search range GUESS: L, middle position of R After the loop: L: left edge of the new search range R: right edge of the new search range GUESS: The new l, r middle position at the end of each loop, the value that we're looking for is either between positions L and R, or it doesn't existCopy the code

Program implementation

    // Search a list of sorted numbers, return index if found, return -1 if not found
    function bSearch(A, x) {
    let l = 0,
        r = A.length - 1,
        guess
    while(l <= r) {
        guess = Math.floor((l + r)/2)
        
        if(A[guess] === x) return guess
        else if(A[guess] < x) l = guess + 1
        else r = guess - 1
    }
    return -1    
}

let arr = [1.2.5.11.12.16]
console.log(bSearch(arr, 11)) // The result is: 3
Copy the code

Insert sort

Imagine this: if your hand is in order, grab one card at a time and insert it into place.

Question: How do I insert a new value into an ordered array and then keep it ordered

Function abstraction

  function insert(A, x)
  A: sorted arrayx: Returned value of the element to be inserted: NoneCopy the code

First edition:

  const A = [2.4.7.9.13] /** Original array */
  const x = 8 /** The element to insert */
  const index = A.indexOf(b)
  A.splice(index === -1 ? A.length : index, 0, x)
  console.log(A) // [2, 4, 7, 8, 9, 13]
Copy the code

Cyclic invariant

P: points to the next element to be compared. P +1: points to the space vacated. I: points to the next element to be sortedCopy the code

The second version:

  function insert(A, i, x) {
    let p = i - 1
    while(A[p] > x) {
      A[p + 1] = A[p]
      p--
    }
    A[p + 1] = x
  }

  function insert_sort(A) {
    for (const i of A.keys()) {
      insert(A, i, A[i])
    }
  }
  const  A = [1.2.100.11.12.16]
  insert_sort(A)
  console.log(A) // [1, 2, 11, 12, 16, 100]
Copy the code

Bubble sort

You can imagine, under a lake, you have a bunch of bubbles of different sizes coming up, and which of them is going to get to the surface first because physics says the biggest one gets to the surface first

Problem: according to the principle of bubbling to achieve sorting…

Problem abstraction:

  function bubble_sort(A)
  A: The array to sort returns: noneCopy the code

Cyclic invariant

Outer loop invariant: after the KTH loop, the first k values are sorted in position I. After the loop is executed, position I and the value to its right are in the sorted state inner loop invariant: at the end of each loop, the control variable j points to the largest value in the 0-j elementCopy the code

Program implementation:

  function swap(A, i, j) {
    const temp = A[i]
    A[i] = A[j]
    A[j] = temp
  }

  function bubble_sort(A) {
    for (let i = A.length; i >= 1; i--) {
      for (let j = 1; j <= i; j++) {
        A[j - 1] > A[j] && swap(A, j - 1, j)
      }
    }
  }
  const A = [1.2.100.11.8.16]
  bubble_sort(A)
  console.log(A) //[1, 2, 8, 11, 16, 100]
Copy the code

Merge sort

Problem: The implementation keeps splitting the array and then merging it

Problem abstraction:

  function merge(A, p, q, r)
  
  AAn array of:p: left half starting positionq: Left half end, right half start positionr: End on the right sideCopy the code

Cyclic invariant:

I: points to the next element to be put back in A1. J: points to the next element to be put back in A2. K: points to the next writeback position in ACopy the code

Program implementation:

  function merge(A, p, q, r) {
    const A1 = A.slice(p, q)
    const A2 = A.slice(q, r)
    A1.push(Number.MAX_SAFE_INTEGER)
    A2.push(Number.MAX_SAFE_INTEGER)
    for (let k = p, i = 0, j = 0; k < r; k++) {
      A[k] = A1[i] < A2[j] ? A1[i++] : A2[j++]
    }
  }
  
  function merge_sort(A, p, r) {
    if(r - p < 2) return
    let q = Math.ceil((r + p)/2)
    merge_sort(A, p, q)
    merge_sort(A, q, r)
    merge(A, p, q, r)
  }
  const A = [1.2.60.19.8.16]
  merge_sort(A) // [1, 2, 8, 16, 19, 60]
  merge_sort(A, 3.5) // [1, 2, 60, 8, 19, 16]
Copy the code

Quick sort

Split the array by center, putting values <= center to the left and values greater than center to the right

Problem abstraction:

  function partition(A, lo, hi)
    A: The array to sortlo: Starting position (Closed interval)
    hi: End position (Open interval) return: center location Side effect: [lo.hiDivided into two areas by a central pointfunction qsort(A)
  A: The array to sort returns: noneCopy the code

Cyclic invariant:

We need to determine: <= center point: [LO, I) undefined: [I, j) greater than center point: [j, hi) Center point: hi-1Copy the code

Program implementation:

  function partition(A, lo, hi) {
    const pivot = A[hi - 1]
    let i = lo, j = hi -1
    while(i ! == j) { pivot >= A[i] ? i++ : swap(A, i, --j) } swap(A, j, hi -1)
    return j
  }
  
  function swap(A, i, j) {
    [A[i], A[j]] = [A[j], A[i]]
  }
  
  function qsort(A, lo = 0, hi = A.length) {
    if (hi - lo < 2) return
    let pivot = partition(A, lo, hi)
    qsort(A, lo, pivot)
    qsort(A, pivot + 1, hi)
  }
  const A = [100.2.60.19.8.16]
  qsort(A) // [2, 8, 16, 19, 60, 100]
Copy the code

Counting sort

Iterate over the original array, accumulative write accumulative array. Then add and accumulate the array to get the element position.

Problem abstraction:

  function counting_sort(A)
  A; The array to be sorted returns: result arrayCopy the code

Program implementation:

  function counting_sort(A) {
    const max = Math.max(... A)// Accumulate the array
    const B = Array(max + 1).fill(0)
    // Result array
    const R = Array(A.length)
    // Cumulative array increment
    A.forEach((_, i) = > B[A[i]]++)
    // Add the sum
    for (let i = 1; i < B.length; i++) {
      B[i] += B[i-1]}for (const i of A.keys()) {
      const p = B[A[i]] - 1 // Write back position
      B[A[i]]-- // New write position
      R[p] = A[i] // Write back the result
    }
    return R
  }
  const A = [9.2.60.19.8.16]
  console.log(counting_sort(A)) //[2, 8, 9, 16, 19, 60]
Copy the code

Radix sort

Sort integers by grouping values of the same significant digit.

Problem abstraction:

  function radix_sort(A) {
    for (let i ofThe number of digits in A ()) {sort by the ith significant digit of the left number A}}Copy the code

Program implementation:

  function radix_sort(A) {
    const max = Math.max(... A)const buckets = Array.from({ length: 10 }, () = > [])
    // Significant digits
    let m = 1
    while(m < max) {
      // Put the array into the bucket
      A.forEach( num= > {
        const digit = ~~ ( ( num % ( m * 10 )) / m )
        buckest[digit].push(num)
      })
      // Fetch the element from the bucket
      let j = 0
      buckets.forEach( bucket= > {
        while(bucket.length > 0) {
          A[j++] = bucket.shift()
        }
      })
      // Next position
      m *= 10}}const A = [9.2.600.19.8.16]
  radix_sort(A  )
  console.log((A)) // [2, 8, 9, 16, 19, 600]
Copy the code

Bucket sort

Counting sort is a special kind of bucket sort.

Problem abstraction:

  function bucket_sort(A, K, S)
  A: The array to sortK: Number of bucketsS: Size of each bucket returns: sorted arrayCopy the code

Program implementation:

  function bucket_sort(A, K, S) {
    const buckets = Array.from({ length: K }, () = > [])
    // Put it in the bucket
    for (let i of A.keys()) {
      const index = ~~(A[i] / S)
      buckets[index].push(A[i])
    }
    // Sort each bucket
    for (let i of buckets.keys()) {
      insertion_sort(buckets[i])
    }
    // Retrieve data
    return[].concat(... buckets) }function insertion_sort(A) {
    for (let i = 1; i < A.length; i++) {
      let p = i - 1
      const x = A[p+1]
      while(p >= 0 && A[p] > x) {
        A[p+1] = A[p]
        p--
      }
      A[p+1] = x
    }
  }
  const A = [9.2.600.19.80.16]
  console.log(bucket_sort(A, 10.100)) // [2, 9, 16, 19, 80, 600]
Copy the code

External sort

Usage scenario: Large hard disk, small memory.

For example: need to sort 600M data, at this time only 300M memory, and the hard disk has 500GB…

For external sort, the performance of sorting algorithm is no longer the biggest bottleneck; The bottleneck of the algorithm is data read and write (I/O). Since memory reads and writes occur in nanoseconds, hard disk reads and writes occur in milliseconds, and hard disk reads and writes are a physical process

External sorting occurs on disk, not in memory.