“This is the 29th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

Today we’re going to review the basic sorting algorithm

  • Bubble sort
  • Insertion sort
  • Selection sort
  • Advanced sorting algorithm
  • Merge sort
  • Quick sort

Step by step, and then what will the interviewer ask

Sorting algorithm

Bubble sort

steps

  • 1. Starting with the first element, compare every two adjacent elements, and if the former is large, switch places
  • 2. After each traversal, the maximum value of the traversal elements can be found
  • 3. If there are unsorted elements, proceed to 1

The demo

Basic writing

export const bubbleSort = function (nums) {
    // Cache array length
    const len = nums.length;
    // Bubble sort is O(n^2), so there are two for loops
    // The first level loop can place the largest value at the end of the array each time
    for (let i = 0; i < len; i++){
        // The second value only needs to be traversed len-i times because the largest value is already at the end of the array
        // The second loop is for swaps
        for (let j = 0; j < len - i; j++){if (nums[j] > nums[j + 1]) {
            //js unique exchange mode
                [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]; }}}return nums;
}
Copy the code
  • Time complexity: O(n^2), two for loops, and both can execute at most n times, so complexity is O(n^2).
  • Space complexity: O(1), the space of that variable is not expanded, so the space complexity is O(1).

So let’s think about whether it’s a little bit redundant to loop through this array twice if it’s already ordered, so we can add a flag bit to see if this array is already ordered, just to reduce the time complexity

Advanced writing

Adding flag bits is also called the sentry method

function betterBubbleSort(arr) {
    const len = arr.length  
    for(let i=0; i<len; i++) {// The difference here is that we add a flag bit
        let flag = false
        for(let j=0; j<len-1-i; j++) {if(arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
                // When a swap occurs, the flag bit is modified
                flag = true}}// If no swap occurs, the array is in order
        if(flag == false) return arr;
    }
    return arr
}
Copy the code

In this case, the best case time is order n.

Selection sort

steps

  • 1. Take the first element of the unsorted part, traverse the rest of the element and compare the size. So for the first iteration, you take the first element
  • 2. If there is a smaller, swap places with that element
  • 3. Each iteration can find the minimum value of the remaining elements and put it at the end of the sorted part

The demo

writing

const selectSort = (arr) = > {
    // No operator "<" can be applied to type "undefined" errors in JavaScript, as you find in other type languages. Therefore, JavaScript evaluates incompatible types with operators as false.
    for (let i = 0; i < arr.length; i++) {
        // The minimum initialization value is I
        let min = i;
        // Find the minimum coordinate of the unsorted part
        for (let j = i; j < arr.length; j++) {
             if(arr[min] > arr[j]) { min = j; }}// If the minimum coordinate is not the original coordinate, then switch positions
        if (min !== i) {
            [arr[i], arr[min]] = [arr[min], arr[i]];
        }
    }
    return arr;
};
Copy the code

  • Time complexity: O(n^2), two for loops, maximum time complexity O(n^2)

  • Space complexity: O(1)

  • And bubble sort difference: bubble sort is to put the largest bubble sort, selection sort is to put the smallest selection first

Insertion sort

steps

  • 1. Divide a set of data to be sorted into two sections. One section is sorted data, and the other section is unsorted data.
  • 2. Insert an element from the “unsorted” data into the correct position in the “sorted” data (which may involve moving the original element), and the “sorted” data will remain in order after insertion.
  • 3. As long as the loop continues until all “unsorted” data has been fetched, the whole sorting is complete.

The demo

writing

export const insertSort = (arr) = > {
    // The time complexity is O(n^2)
    // Why is I 1 here, because we need to split the unsorted ones into two segments, starting with 1, leaving one for the sorted ones
    for (let i = 1; i < arr.length; i++) {
        // The sorted part is sorted backwards
        // If the current one is larger than the previous one, then swap
        // We want to know which two are swapped for the first time, the last one sorted, and the first one unsorted
        for (let j = i - 1; j >= 0; j--) {
            // Always use the preceding and the following comparison
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; }}}return arr;
};
Copy the code
  • Time complexity: O(n^2), the outer loop is at most N, the inner loop is at most N, then the time complexity is still O(n^2).
  • Space complexity: O(1), there’s nothing to say

conclusion

Today we talked about bubble sort, select sort, insert sort, you must study carefully, you must remember when learning things, how to learn when you can still remember what you learned today after 100 days, so you must learn thoroughly, not fast, right