Introduction to Sorting Algorithm (JavaScript)

Introduction to Sorting Algorithm (JavaScript)

Introduce

Convert a list of data in a disordered state into an ordered state. Such as:

Number sequence : 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 sort

O(n), O(nk) :

  1. Bucket sorting
  2. Base sort

Comparison/other

Based on comparison :

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

Other :

  1. Bucket sorting
  2. Base sort

According to whether to open up a new space classification

In-situ (swap in-situ without opening up memory space) :

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

Off-site :

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

achieve

Binary search

Imagine: If you are a teacher and you want to find a certain test paper among a bunch of test papers, what would you do to find it in the shortest time.

abstract

function bsearch ( A, x ) A : Array x : the value to be found Returns: X in the A position, there is no return -1 duplicated code

Loop invariant

Before the cycle: l means: the left boundary of the search range r means: the right boundary of the search range guess means: the middle position of l and r After the loop: l means: the left boundary of the new search range r means: the right boundary of the new search range guess means: the new l, the middle position of r After the end of each cycle, the searched value is either between the positions lr or does not exist Copy code

Program realization

//Search in a set of sorted numbers, if found, return to the index and 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 } the let ARR = [ . 1 , 2 , . 5 , . 11 , 12 is , 16 ] Console .log (bsearch (ARR, . 11 )) //Result: 3 copy the code

Insert sort

It is conceivable: If the cards in your hand are in order, draw one card at a time and insert it into the corresponding position.

Question: How to insert a new value in an ordered array, and then it will still be ordered

Function abstraction

function insert ( A, x ) A : sorted array x : element to be inserted Return value: None Copy code

First edition:

const A = [ 2 , 4 , 7 , 9 , 13 ] /** Original array*/ const x = 8 /** Elements to be inserted*/ const index = A.indexOf(b) A.splice (index === - . 1 A.length:? Index, 0 , X) Console .log (A) //[2,. 4,. 7,. 8,. 9, 13 is] copy the code

Loop invariant

p: points to the next element to be compared p+1: point to the vacant space i: point to the next element to be sorted Copy code

second edition:

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 is, 16, 100] copy the code

Bubble sort

It is conceivable that under a lake, there is a bunch of bubbles of different sizes rising upwards, so which one of them will reach the level first. According to the principles of physics, the largest one will reach the surface first.

Question: Sort according to the principle of bubbling...

Problem abstraction:

function bubble_sort ( A ) A : the array to be sorted Return: None Copy code

Loop invariant

Outer loop invariant: After the k-th loop is executed, the top k values are sorted at position i in order. After the loop is executed, the position i and the value to the right of it are in a sorted state The inner loop invariant: At the end of each loop, the control variable j points to the largest value among elements 0-j Copy code

Program realization:

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: Realize that the original array is continuously split, and then merged

Problem abstraction :

function merge ( A, p, q, r ) A : Array P : the left half of the starting position Q : the end of the left half and right half of the start position of R & lt : End right half duplicated code

Loop invariant :

i: point to the next element to be replaced in A1 j: point to the next element to be replaced in A2 k: point to the next write-back position in A Copy code

Program realization :

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 according to the center point, put the value of <= center point to the left of the center point, and place the value greater than the center point on the right

Problem abstraction :

function partition ( A, lo, hi ) A : array to be sorted lo : start position ( closed interval ) hi : end position ( open interval ) Return: The location of the center point Side effect: [ lo , hi ] is divided into two areas by the center point function qsort ( A ) A : the array to be sorted Return: None Copy code

Loop invariant :

We need to determine: <=Center point: (lo, i) Not determined: (i, j) Greater than the center point: (j, hi) Center point: hi-1 Copy 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

Traverse the original array and write cumulatively into the cumulative 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: the result array Copy code

Program implementation :

function counting_sort(A) { const max = Math.max(...A) // const B = Array(max + 1).fill(0) // const R = Array(A.length) // A.forEach((_, i) => B[A[i]]++) // 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 // B[A[i]]-- // R[p] = A[i] // } return R } const A = [9, 2, 60, 19, 8, 16] console.log(counting_sort(A)) //[ 2, 8, 9, 16, 19, 60 ]

(radix sort)

:

function radix_sort(A) { for (let i of A ()) { i A } }

:

function radix_sort(A) { const max = Math.max(...A) const buckets = Array.from({ length: 10 }, () => []) // let m = 1 while(m < max) { // A.forEach( num => { const digit = ~~ ( ( num % ( m * 10 ))/m ) buckest[digit].push(num) }) //Take out 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

Count sorting is a special bucket sorting.

Problem abstraction :

function bucket_sort ( A, K, S ) A : the array to be sorted K : the number of buckets S : the size of each bucket Returns: sorted array Copy code

Program implementation :

function bucket_sort ( A, K, S ) { const buckets = Array .from({ length : K }, () => []) //put 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]) } //Take out the 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

Application scenario: The hard disk is large and the memory is small.

For example: Need to sort 600M data, then the memory is only 300M, and the hard disk has 500G...

For external sorting, the performance of the sorting algorithm is no longer the biggest bottleneck; the bottleneck of the algorithm is data read and write (I/O). Because the read and write of the memory is in the nanosecond level, the read and write of the hard disk is in the millisecond level, and the hard disk reads data is a physical process

The external sorting occurs on the disk, not on the memory. The program implementation is slightly...