Starter – sorting algorithm

Hello, brave friends, I am your strong mouth king xiao Wu, healthy body, not brain disease.

I have a wealth of hair loss techniques that will catapult you to the top.

A look will be written waste is my theme, food to pick the foot is my characteristics, humble in showing a trace of strong, stupid people have stupid blessing is the greatest comfort to me.

Welcome to the beginning of the fifth algorithm series – sorting algorithm.

preface

This series of articles to “algorithm diagram” and “Learning JavaScript algorithm” two books as the core, the rest of the materials as assistance, and with the author’s insights. Strive to simple, interesting language to bring everyone to appreciate the magic of this algorithmic world. In this series of articles, one by one, we use the sorting algorithm to open the first chapter of the great voyage.

This article covers the following five common sorts: three simple sorts: “bubble sort,” “selection sort,” “insertion sort,” and two more complex sorts: “Quicksort,” and “merge sort.”

Each sort is described in detail in five parts: basic idea, process diagram, algorithm analysis, time and space complexity, and code implementation.

< Supplementary instructions > it is recommended to understand the execution order of the program stack, can read the algorithm diagram – 3.3 stack, will make learning fast row and merge twice the result with half the effort; This chapter is mainly used to understand the execution order of recursion. The author thinks that if it is difficult to understand fast sorting and merging, the bottom line is that recursion is not understood thoroughly. This chapter can lay the foundation for the following algorithm learning; 【 Above does not affect the reading of this article, everyone differs from person to person, choose by yourself 】

Bubble sort

👺 Basic idea: < adjacent elements pair contrast to find the maximum >

👺 Process diagram:

👺 algorithm analysis:

1. Outer loop: length – 1 times

2. Inner loop: length-1 – Number of determined elements (equivalent to index of outer loop) times

3. If arr[j] > ARr [j + 1], then swap elements

👺 Complexity:

According to above analysis, the outer loop n – n – 1 n – 1, the inner loop (n – 1) / 2 (n – 1) / 2 (n – 1) / 2 times, so the total number of executions is 2/2 (n – 1) (n – 1) ^ 2/2 2/2 (n – 1)

Tips: Neither time complexity nor space complexity cares about low-order variables, coefficients, and constants

Time complexity: the highest term above is N2n ^2n2, so the time complexity is O(n2)O(n^2)O(n2).

Space complexity: only the temp variable requires memory space, so the space complexity is O(1)O(1)O(1)

👺 code implementation:

const bubbleSort = (arr: number[]) = > {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp; }}}return arr;
}
Copy the code

Selection sort

👺 Basic idea: < select the minimum value in order >

👺 Process diagram:

👺 algorithm analysis:

1. Outer loop: length – 1 times

2. Inner loop: start at I + 1 and loop length – (I + 1) times

3. Record that the index of the outer loop is minIndex. If a smaller value is found in the inner loop, update minIndex

4. Swap arR [index] and ARR [minIndex]

👺 Complexity:

According to above analysis, the outer loop n – n – 1 n – 1, the inner loop (n – 1) / 2 (n – 1) / 2 (n – 1) / 2 times, so the total number of executions is 2/2 (n – 1) (n – 1) ^ 2/2 2/2 (n – 1)

Time complexity: O(n2)O(n^2)O(n2)

Space complexity: temp and minIndex variables require memory space, because they don’t care about coefficients, so O(1)O(1)O(1)

👺 code implementation:

const selectSort = (arr: number[]) = > {
  let minIndex: number;

  for (let i = 0; i < arr.length; i++) {
    minIndex = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) minIndex = j;
    }
    
    let temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
  }

  return arr;
}
Copy the code

Insertion sort

👺 Basic idea: < from left to right in order to confirm the location of elements >

👺 Process diagram:

👺 algorithm analysis:

1. Outer loop: the loop starts from 1, and the number of loops is length-1

2. Inner loop: loop from j = I, one by one with the previous term, less than the previous term interchange, until inserted in the correct position

👺 Complexity:

According to the above analysis, the outer loop is n−1n-1n−1 and the inner loop is n/2n/2n/2, so the total number of executions is N ∗(n−1)/2n * (n-1)/2n ∗(n−1)/2

Time complexity: O(n2)O(n^2)O(n2)

Space complexity: only the temp variable requires memory space, so it is O(1)O(1)O(1)

👺 code implementation:

const insertSort = (arr: number[]) = > {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      if (arr[j - 1] > arr[j]) {
        let temp = arr[j - 1];
        arr[j - 1] = arr[j]; arr[j] = temp; }}}return arr;
}
Copy the code

Quick sort

👺 Basic idea: < grouping left and right by the baseline value and then merging > (we select the middle item of the array as the baseline value)

👺 Process diagram:

👺 algorithm analysis:

1. The idea of quicksort is to use a value as a reference, less than the reference value is pushed into the left array, greater than the reference value is pushed into the right array; Recursive calls until the array is empty; The left and right arrays and the reference values are spliced, and the required array is formed after all the splicing;

2. Get middle from splice and math.floor (arr.length / 2);

3. Understand the call order of the stack, can understand quicksort;

👺 Complexity:

The complexity of recursive process divided by base value in half is lognlognlogn; The complexity of the for loop is NNN

Time complexity: O(nlogn)O(nlogn)O(nlogn)

Space complexity: Space complexity is the number of recursive levels -> O(logn)O(logn)O(logn)

👺 code implementation:

const quickSort = (arr: number[]) :number[] = > {if(! arr.length)return [];

  let leftArr: number[] = [];
  let rightArr: number[] = [];
  let middle = arr.splice(Math.floor(arr.length / 2), 1) [0];
  
  arr.forEach(item= > {
    item < middle ? leftArr.push(item) : rightArr.push(item);
  })

  return quickSort(leftArr).concat(middle, quickSort(rightArr));
}
Copy the code

Merge sort

👺 Basic idea: < Merge ordered arrays into larger ordered arrays >

👺 Process diagram:

👺 algorithm analysis:

1. Merge sort uses the idea of divide and conquer, that is, decompose the original problem into subproblems, solve the subproblems and merge the subproblems; Therefore, decompose the large array into small arrays until there is only one element in the array. At this time, the array is all ordered. Merge and sort the ordered array to form a new ordered array.

2. Floor (arr.length / 2) is used to get the index of the intermediate item, and the array is split into two by index and slice.

3. When merging, compare the first item in the left and right arrays, push the smaller value into the new array, and update the left and right arrays with shift.

4. Understand the call order of the stack, can understand merge sort;

👺 Complexity:

【分】 binary operation -> complexity is lognlognlogn; 【合】while loop -> NNN;

Time complexity: O(nlogn)O(nlogn)O(nlogn)

Space complexity: Space complexity is the number of recursive layers and the space occupied by temporary arrays -> logn+nlogn+nlogn+n, so the space complexity is O(n)O(n)O(n)

👺 code implementation:

const mergeSort = (arr: number[]) :number[] = > {/ / split
  if (arr.length <= 1) return arr;

  let middle = Math.floor(arr.length / 2);
  let leftArr = arr.slice(0, middle);
  let rightArr = arr.slice(middle);

  return merge(mergeSort(leftArr), mergeSort(rightArr));
}

const merge = (leftArr: number[], rightArr: number[]) = > { / / merge
  let result: number[] = [];

  while (leftArr.length || rightArr.length) {
    if (leftArr.length && rightArr.length) {
      leftArr[0] < rightArr[0]? result.push(leftArr.shift()as number)
        : result.push(rightArr.shift() as number);
    } else {
      if (leftArr.length) result.push(leftArr.shift() as number);
      if (rightArr.length) result.push(rightArr.shift() as number); }}return result;
}
Copy the code