This is the twelfth day of my participation in the August More Text Challenge. For details, see “August More Text Challenge”.

Hi, today we’re going to talk about quicksort, a better sort algorithm. Let’s get started! Let ‘s go!

Quick sort

Quicksort performs better than bubble sort, selection sort, and insert sort. It is also a practical sort algorithm, which Chrome used as its sort algorithm.

Quick sort idea

  • Partition: Select any reference from the array. All elements smaller than the reference are placed before the reference and all elements larger than the reference are placed after the reference.

  • Recursion: Recursively partition subarrays before and after the base.

Quicksort animation

Quicksort animation

  • First select any one in the array as the benchmark, and since it is arbitrary, use the first one in the array as the benchmark.

  • Yellow is the current benchmark.

  • The array is then compared one by one, with the current element in red.

  • Larger than the base is purple and smaller is green.

  • After one loop, insert the benchmark behind all the greens.

  • The partition operation is complete.

  • Next, recursively perform the above partition operation for the first and second partitions.

  • And I’m done sorting.

implementation

Array.prototype.quickSort = function () {
    const rec = arr => {
        if (arr.length= = =1) return
        const left = []
        const right = []
        const mid = arr[0]
        for (let i = 1; i < arr.length; i++) {
            if (arr[i] < mid) {
                left.push(arr[i])
            } else {
                right.push(arr[i])
            }
        }
        return [...rec(left), mid, ...rec(right)]
    }
    const res = rec(this)
    res.forEach((n, i) => { this[i] = n })
}
const arr = [3.44.38.5.47.15.36.26.27.2.46.4.19.50.48]
arr.quickSort()
console.log(arr);
/ / /
   2.3.4.5.15.19.26.27.36.38.44.46.47.48.50
]

Copy the code

The time complexity of quicksort

  • The time for recursion is order logN.

  • The time complexity of the partition operation is O (n).

  • Time complexity: O (n * logN).

End~~~