Quicksort – Use a divide and conquer strategy

Conclusion:

  • Divide and conquer: a famous recursive problem solving idea
  • Euclid algorithm: also known as division, a common and practical algorithm idea
  • Euclid’s algorithm

    Also known as division, is a common method of finding the greatest common divisor

    How to divide the larger number by the smaller number, then divide the divisor by the remainder that appears (the first remainder), then divide the first remainder by the remainder that appears (the second remainder), and so on until the remainder is 0, and the final divisor is the largest common divisor

    A divided by B is the same thing as B divided by A, which is B divided by A

Note: For example, if (25,10) -> (25/10=2 remainder 5) -> (10/5=0 remainder 0), the largest common divisor is the last divisor is 5.

Euclidean algorithm is implemented in code as follows

    function Euclid(x, y) {
        let r = x > y ? x % y : y % x;
        let min = x > y ? y : x;
        if (r == 0) {
            return min;
        } else {
            return Euclid(min, r)
        }
    }
/** Simplified version */
    function Euclid(a, b) {
        return b === 0 ? a : Euclid(b, a % b);
    }
    Euclid(25.10)/ / - 5
Copy the code

Use recursive functions to get the sum of arrays/the maximum value of arrays, etc

    function getSum(arr) {
        If (arr.length>1){return arr.shift()*1+getSum(arr)*1}else{return arr[0]} */
        // The above code can be abbreviated as follows
        return arr.length == 1 ? arr[0] : arr.shift() + getSum(arr)
    }
    var arr = [2.4.5.7.5.6.2.3]
    getSum(arr)

    function getMax(max, arr) {
        if (arr.length > 1) {
            // If the current maximum value is larger than the first item of the array, keep it; otherwise, assign a new value
            max = max > arr[0]? max : arr[0];
            arr.shift()
            return getMax(max, arr)
        } else
            return max
    }
    var arr2 = [2.4.5.7.5.6.2.3]
    getMax(0, arr2)
Copy the code

Quick sort

1. The speed of the algorithm refers not to the time, but to the increase in the number of operands.

2. When you talk about the speed of an algorithm, you’re talking about how fast its running time will increase as the input increases.

3. The running time of the algorithm is expressed in big O notation.

Order log n is faster than order n, and the more elements you have to search for, the faster the former is.

Note: C standard library function qsort is the implementation of quicksort, quicksort also uses D&C.

Let’s talk about big O notation

  • What is unique about quicksort is that its speed depends on the selected reference value
  • In general, using big O notation ignores constants, which don’t matter for large orders of magnitude
  • So let’s look at the big O notation for the common algorithm
algorithm O said
Binary search O( logn )
Easy to find O( n )
Quick sort O(n logn )
Selection sort O (n squared)
Traveling salesman problem algorithm O( n! )
  • There’s also a sort algorithm called merge sort, which takes order nlogn.

In quicksort

  • Quicksort because performance depends on the selected reference value
  • Therefore, there are mean – case and worst – case scenarios
  • Case 1:
    • If the first element is always selected as the reference value and the array is processed in order
    • The height of the call stack is n, and the worst case call stack is O(n).
  • Situation 2:
    • If you always choose the middle element as the reference value
    • Then the height of the call stack is n over 2, and the best case is O(logn).

So in the best case, the height of the call stack is O(logn), it takes O(n) time per layer and the running time of this algorithm is O(logn)*O(n)=O(nlogn).

In the worst case, the height of the call stack is O(n), it takes O(n) time per layer and the running time of this algorithm is O(n)*O(n)=O(n²).

Note: the best case is also the average case. The average running time of quicksort is O(nlogn).

conclusion

It can be seen from the above:

  • When implementing random sorting, please randomly select the reference value elements, and the average running time of quicksort is O(nlogn).
  • For simple and binary search, the steady on is negligible, and when the list is long, O(logn) is much faster than O(n).

You may also be interested in the following

  • # Diagram Algorithm 1 (arrays and linked lists in memory)
  • # Algorithm Diagram 2 (recursion and call stack in memory)
  • # Algorithm Figure 4 (hash table and loading factor)
  • # JavaScript Language Essence
  • How are some of the apis implemented in # VUE3.0?
  • JavaScript reads local file configuration (compatible with lower IE versions)
  • # What do you ask about the front end of one year’s work experience?