# 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 ]
```

:

```  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 ]
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...