Sorting of "beauty of algorithm series" (JS version)

wuwhs 2021-11-25 17:41:03

Preface

Recently, I've been ( Enter into ) Ten ( door ) Algorithm , I can only take notes for a little comfort , Record and share here , It will be summarized into a series later . such as 「 Recursion and backtracking 」、「 Depth and breadth first 」、「 Dynamic programming 」、「 Two point search 」 and 「 greedy 」 etc. .

Bubble sort (Bubble Sort)

Basic idea of bubble sorting

Given an array , We pour all the elements in the array into the pool , These elements will be compared with each other , In order of size, one by one, it surfaced like bubbles .

Bubble sort implementation

Every round , Start with the messy array header , Every two elements are compared in size and exchanged , Until the largest or smallest element in this round is placed at the end of the array , Then repeat the process , Until all the elements are in place . among , The core operation is to compare elements with each other .

Bubble sorting example analysis

Given array [2, 1, 7, 9, 5, 8], From left to right 、 Sort from small to large .

Bubble sorting problem solving ideas

Bubble from left to right , Move the larger number to the right .

bubble-sort

  • First, the pointer points to the first number , Compare the size of the first number and the second number , because 2 Than 1 Big , So swap two ,[1, 2, 7, 9, 5, 8].
  • Next, the pointer moves one step forward , Compare 2 and 7, because 2 Than 7 Small , Both remain stationary ,[1, 2, 7, 9, 5, 8]. up to now ,7 It's the largest number .
  • The pointer continues to move forward , Compare 7 and 9, because 7 Than 9 Small , Both remain stationary ,[1, 2, 7, 9, 5, 8]. Now? ,9 Became the largest number .
  • Further back , Compare 9 and 5, Obviously ,9 Than 5 Big , Exchange their positions ,[1, 2, 7, 5, 9, 8].
  • Last , Compare 9 and 8,9 Than 8 Big , Exchange their positions ,[1, 2, 7, 5, 8, 9]. After the first round of pairwise comparison ,9 The largest number appears at the end of the array like a bubble .
  • Next, let's make a second round of comparison , Re point the pointer to the first element , Repeat the above , Last , The array becomes :[1, 2, 5, 7, 8, 9].
  • In a new round of comparison , Judge whether there was a pairwise exchange in the last round of comparison , If an exchange doesn't happen , It proves that the array is in order .

Bubble sort code example

// Bubble sort algorithm
const bubbleSort = function (arr) {
const len = arr.length
// Mark whether each round occurs to exchange
let hasChange = true
// If there is no exchange, it is already in order , Just jump out of the outer layer
for (let i = 0; i < len && hasChange; i++) {
hasChange = false
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
hasChange = true
}
}
}
}
const arr = [2, 1, 7, 9, 5, 8]
bubbleSort(arr)
console.log('arr: ', arr)

Analysis of bubble sort algorithm

Bubble sort space complexity

Suppose the number of elements in the array is n, Because in the whole sorting process , We exchange elements directly in a given array , So the spatial complexity is O(1).

Bubble sort time complexity

The given array has been arranged in order

  • under these circumstances , We just need to do n−1 The second comparison , The number of pairwise exchanges is 0, The time complexity is O(n). This is the best case .
  • The given array is arranged in reverse order . under these circumstances , We need to do n(n-1)/2 Compare it to , The time complexity is O(n2). This is the worst case scenario .
  • The given array is messy . under these circumstances , The average time complexity is O(n2).

thus it can be seen , The time complexity of bubble sorting is O(n2). It's a stable sort algorithm .( Stability means that if there are two equal numbers in the array , Then the relative positions of these two equal numbers before and after sorting remain unchanged .)

Insertion sort (Insertion Sort)

The basic idea of insertion sort

Continuously insert numbers that have not been ordered into the ordered parts .

Insert sort feature

In bubble sorting , After each round of sorting , The numbers at the back end of the array are in good order ; For insert sort , After each round of sorting , The numbers at the front of the array are in good order .

Insert sorting example analysis

An array [2, 1, 7, 9, 5, 8] Insert sort .

Insert sorting problem solving ideas

  • First, divide the array into left and right parts , On the left is the ordered part , On the right is the part that hasn't been arranged yet , At first , The ordered part on the left has only the first element 2. Next , We deal with the elements on the right one by one , Put them on the left .

insertion-sort

  • First look 1, because 1 Than 2 Small , Need to put 1 Insert into 2 In front of , It's easy to do , Just switch positions in pairs ,[1, 2, 7, 9, 5, 8].
  • then , We are going to put 7 Insert into the left part , because 7 Have more than 2 big , That means it's the biggest element right now , Keep the position ,[1, 2, 7, 9, 5, 8].
  • Empathy ,9 There is no need to change the position ,[1, 2, 7, 9, 5, 8].
  • Next , How to make 5 Insert in place . Compare first 5 and 9, because 5 Than 9 Small , In exchange ,[1, 2, 7, 5, 9, 8], continue , because 5 Than 7 Small , In exchange ,[1, 2, 5, 7, 9, 8], Last , because 5 Than 2 Big , This round is over .
  • The last number is 8, because 8 Than 9 Small , In exchange ,[1, 2, 5, 7, 8, 9], Compare again 7 and 8, Find out 8 Than 7 Big , This round is over . Here we are , Insert sort complete .

Insert sort code example

// Insertion sort
const insertionSort = function (arr) {
const len = arr.length
for (let i = 1; i < len; i++) {
let current = arr[i]
for (let j = i - 1; j >= 0; j--) {
// current Less than j The value pointing to the left of , take j Point to the left and shift the value one bit to the right
if (current < arr[j]) {
arr[j + 1] = arr[j]
} else {
// Otherwise it would be current Insert into j Location , Jump out of the inner loop
arr[j] = current
break
}
}
}
}
const arr = [2, 1, 7, 9, 5, 8]
insertionSort(arr)
console.log('arr: ', arr)

Insert sort algorithm analysis

Insert sort space complexity

Suppose the number of elements in the array is n, Because in the whole sorting process , Is to exchange elements directly in a given array , The space complexity is O(1).

Insert sort time complexity

  • The given array has been arranged in order . Just do it n-1 The second comparison , The number of pairwise exchanges is 0, The time complexity is O(n). This is the best case .
  • The given array is arranged in reverse order . under these circumstances , We need to do n(n-1)/2 Compare it to , The time complexity is O(n2). This is the worst case scenario .
  • The given array is messy . under these circumstances , The average time complexity is O(n2).

thus it can be seen , It's the same as bubbling , The time complexity of insertion sort is O(n2), And it is also a stable sorting algorithm .

Merge sort (Merge Sort)

The basic idea of merge sort

The core is divide and conquer , Is to divide a complex problem into two or more identical or similar subproblems , Then divide the subproblem into smaller subproblems , Until the subproblem can be simply solved directly , The solution of the original problem is the combination of the solutions of the subproblems . Merging and sorting embody the idea of division and rule incisively and vividly .

Merge sort implementation

First, divide the array into two sub arrays from the middle , Always recursively divide the subarray into smaller subarrays , Until there is only one element in the subarray , Just start sorting .

The way to sort is to merge two elements in size order , Then, according to the recursive return order , Constantly merge ordered subarrays , Until the end, put the whole array in order .

Merge sort code example

// Merge sort
const mergeSort = function (arr, lo, hi) {
if (lo === undefined) {
lo = 0
}
if (hi === undefined) {
hi = arr.length - 1
}
// Determine if the last element is left
if (lo >= hi) return
// Divide the array into two parts from the middle
let mid = lo + Math.floor((hi - lo) / 2)
console.log('mid', mid)
// Recursively arrange the left and right sides respectively
mergeSort(arr, lo, mid)
mergeSort(arr, mid + 1, hi)
// Merge the ordered left and right halves
merge(arr, lo, mid, hi)
}
const merge = function (arr, lo, mid, hi) {
// Copy an original array
const copy = [...arr]
// Define a k The pointer indicates where to start modifying the original array ,
// i The pointer indicates the starting position of the left half
// j The pointer is the actual position of the right half
let k = lo
let i = lo
let j = mid + 1
while (k <= hi) {
if (i > mid) {
arr[k++] = copy[j++]
} else if (j > hi) {
arr[k++] = copy[i++]
} else if (copy[j] < copy[i]) {
arr[k++] = copy[j++]
} else {
arr[k++] = copy[i++]
}
}
}
const arr = [2, 1, 7, 9, 5, 8]
mergeSort(arr)
console.log('arr: ', arr)

among ,While Statements are , There are four possible situations .

  • The numbers on the left half are processed , Only the number left on the right half , Just copy the numbers on the right half one by one .
  • The numbers on the right half are processed , Only the number left , Just copy the numbers on the left half one by one .
  • The number on the right is less than the number on the left , Copy the number on the right to the appropriate location ,j The pointer moves forward one bit .
  • The number on the left is less than the number on the right , Copy the number on the left to the appropriate location ,i The pointer moves forward one bit .

Example analysis of merging and sorting

Use the merge sort algorithm to sort the array [2, 1, 7, 9, 5, 8] Sort .

Merging and sorting problem solving ideas

merge-sort

First, keep slicing the array , Until each subarray contains only one element .
Next, the cut sub arrays are merged recursively in size order , The order of recursion is similar to the forward traversal in a binary tree .

  • Merge [2] and [1] by [1, 2].
  • Subarray [1, 2] and [7] Merge .
  • On the right , Merge [9] and [5].
  • Then merge [5, 9] and [8].
  • Final merger [1, 2, 7] and [5, 8, 9] become [1, 2, 5, 8, 9], You can put the whole array in order .

Merge array [1, 2, 7] and [5, 8, 9] The operation steps are as follows .

merge-array

  • Put the array [1, 2, 7] use L Express ,[5, 8, 9] use R Express .
  • When merging , Open up and allocate a new array T Save results , The array size should be the sum of the lengths of the two sub arrays
  • Then subscript ijk Point to the starting point of each array .
  • Next , Compare subscripts i and j Element pointed to L[i] and R[j], Put in subscripts in order of size k Where to point ,1 Less than 5.
  • Move i and k, Continue to compare L[i] and R[j],2 Than 5 Small .
  • i and k Keep moving forward ,5 Than 7 Small .
  • Move j and k, Continue to compare L[i] and R[j],7 Than 8 Small .
  • Now , The array on the left has been processed , Just put the remaining elements of the right array into the result array .

The reason why the merger can succeed , The prerequisite must be that both subarrays are ordered separately .

Merge sort algorithm analysis

Merge sort space complexity

Because of the merger n Elements need to be allocated a size of n Extra array of , After the merger , The space of this array will be freed , So the spatial complexity of the algorithm is O(n). Merge sort is also a stable sort algorithm .

Merge sort time complexity

Merging algorithm is a recursive process .

give an example : The number of elements in the array is n, The time complexity is T(n) Function of .

solution : Scale this to n The problem is divided into two scales, namely n/2 The sub problem of , The time complexity of each subproblem is T(n/2), So the complexity of the two subproblems is 2×T(n/2). When both subproblems are solved , That is, the two subarrays are in order , They need to be combined , Altogether n Elements , You have to do the most every time n-1 The second comparison , So the complexity of merging is O(n). From this, we get the recursive complexity formula :T(n) = 2×T(n/2) + O(n).

For formula solving , Constantly call a scale n The problem is broken down into n/2 The problem of , Until the scale is 1. If n be equal to 2, Just once in a while ; If n be equal to 4, Need points 2 Time . The number of times here is classified according to the change of scale .

And so on , For scale n The problem of , All in all log(n) Slice the size of the layer . On every floor , We all have to merge , The elements involved are actually all the elements in the array , therefore , The merge complexity of each layer is O(n), So the overall complexity is  O(nlogn).

Quick sort (Quick Sort)

The basic idea of quick sort

Quick sort also adopts the idea of divide and conquer .

Fast sort implementation

Filter the original array into two smaller and larger sub arrays , Then recursively sort the two sub arrays .

give an example : Put all the students in the class in a row in order of height .

solution : The teacher first randomly selected the students A, Let all other students and students A Shorter than tall , Than A The short ones are all standing A Left side , Than A The tall ones are all standing in A To the right of . Next , The teacher chose the students from the left to the right B With my classmates C, Then continue to filter and arrange .

In the process of dividing into smaller and larger sub arrays , How to select a reference value ( That is, students A、B、C etc. ) Especially the key .

Quick sort to achieve example analysis

An array [2,1,7,9,5,8] Sort .

Quick sorting problem solving ideas

quick-sort

  • According to the idea of quick sort , First, filter the array into two smaller and larger sub arrays .
  • Randomly select a number from the array as the reference value , such as 7, So the original array is divided into two sub arrays . Be careful : Quick sort is to perform various exchange operations directly in the original array , So when the subarray is split , The arrangement in the original array has also been changed .
  • Next , Select... From the smaller subarray 2 As a reference value , Select... In a larger subarray 8 As a reference value , Continue to split subarrays .
  • Continue to make the number of elements greater than 1 Subarray of , When the number of elements in all subarrays is 1 When , The original array is also ordered .

Quick sort code example

// Quick sort
const quickSort = function (arr, lo, hi) {
if (lo === undefined) {
lo = 0
}
if (hi === undefined) {
hi = arr.length - 1
}
// Determine if there is only one element left , yes , Then return directly
if (lo >= hi) return
// utilize partition Function to find a random reference point
const p = partition(arr, lo, hi)
// Recursively sorts the number of left and right halves of the base point
quickSort(arr, lo, p - 1)
quickSort(arr, p + 1, hi)
}
// Swap array positions
const swap = function (arr, i, j) {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
// Get the location index randomly
const randomPos = function (lo, hi) {
return lo + Math.floor(Math.random() * (hi - lo))
}
const partition = function (arr, lo, hi) {
const pos = randomPos(lo, hi)
console.log('pos: ', pos)
swap(arr, pos, hi)
let i = lo
let j = lo
// Compare each number with the reference value from left to right , If it is smaller than the reference value , Then put it in the pointer i Point to
// After the cycle ,i The number before the pointer is smaller than the reference value
while (j < hi) {
if (arr[j] <= arr[hi]) {
swap(arr, i++, j)
}
j++
}
// The reference value at the end is placed in the pointer i The location of , i The number after the pointer is larger than the reference value
swap(arr, i, j)
// Return pointer i, Position as reference point
return i
}
const arr = [2, 1, 7, 9, 5, 8]
quickSort(arr)
console.log(arr)

Quick sort algorithm analysis

Time complexity of quick sorting

1、 Best case : The selected benchmark values are all the middle numbers of the current subarray .
Such segmentation , It can guarantee that for a scale of n The problem of , Can be uniformly decomposed into two scales of n/2 Sub problem ( Merge sort also uses the same division method ), Time complexity is : T(n)=2xT(n/2) + O(n).

Size it to n The problem of n/2 Two sub questions of , And the benchmark n-1 Compare it to , The complexity is O(n). Obviously , In the best case , The complexity of quick sorting is also O(nlogn).

2、 The worst : The benchmark value selects the maximum and minimum value in the subarray .

Each time, the subarray is divided into two smaller subarrays , The length of one of them is 1, The other one is only shorter than the atomic array 1.

give an example : For arrays , The benchmark values for each selection are 9、8、7、5、2.

solution : The partitioning process is similar to the bubble sorting process .

The algorithm complexity is O(n^2).

Tips : The worst case can be avoided by randomly selecting the reference value .

Quick sort space complexity

Unlike merge sort , Quick sort in the process of each recursion , Just open up O(1) To complete the exchange operation and realize the direct modification of the array , Because the number of recursion is logn, Therefore, its overall space complexity depends entirely on the number of times to stack , therefore , Its spatial complexity is O(logn).

Please bring the original link to reprint ,thank
Similar articles

2021-11-25

2021-11-25

2021-11-25

2021-11-25

2021-11-25