preface

Reading “learning JavaScript data structure and algorithm (3rd edition)” have a feeling that I hope every time learning algorithm can output a blog, income column, check their own learning situation ~ article has a mistake welcome various big god correction, don’t spray, if you want to spray, trouble light, thank you ~

start

Like merge sort, quicksort uses divide-and-conquer to break the original array into smaller ones (but it doesn’t split them up like merge sort does). Quicksort is more complex than the other sorting algorithms we’ve learned so far, but it’s also a process of sorting, regrouping and merging.

It takes a value (n) from the array, iterates through the remaining array with n removed, stores the numbers less than and greater than n in the array left and right, and then merges left, N, and right, recursively repeating the process

Train of thought

For example arrays [7,1,6,5,3,2,4]

  • Score: Take the middle value of 5 as middle and an array with 5 removed
  • Return: the traversal removes the array of 5 and compares it with 5. The push array less than 5 is left, and the push array greater than 5 is right
  • Concat (5,right), the single left and right recursively repeat this step to continue the quicksort, and finally arrange the array

implementation

function quickSort(array) {
    if (array.length <= 1) return array; If the array length is less than 1, no sorting is required
    var left = [],
        right = []; 
    var middle = array.splice(Math.floor(array.length / 2), 1) [0] // Take out the median and remove it in arR
    // Compare the intermediate value with iterating over the elements of the array with the intermediate value removed
    array.forEach(function (e) {
        e >= middle ? right.push(e) : left.push(e); // Group the elements that are compared with middle
    })
    var arr = quickSort(left).concat(middle, quickSort(right)); // Merge the arrays (each unsorted array continues to be sorted recursively)
    return arr;
}
var arr = [7.1.6.5.3.2.4]
console.log(quickSort(arr)) / /,2,3,4,5,6,7 [1]
Copy the code

To optimize the

The above is relatively simple to write, but requires a lot of storage space, after all, it uses closures, so we optimize it to operate directly on the original array, swap addresses, and require no extra storage space

Train of thought

  • Take a first comparisontarget
  • The right array is less thantargetThe value of thearray[r]Assigned toarray[l]
  • Make the left side array greater than or equal totargetThe value of thearray[l]Assigned toarray[r]
  • All the way up to l equals r and out of the loop, everything on the left is less than target, everything on the right is less than target
  • Through recursion, the left and right sides of the array continue to do a quick sort and return until the array sorted correctly
function quickSort2(array, start, end) {
    if (end - start < 1) return;
    var l = start, // Assume the left array starts at index 0
        r = end; // The right array starts with index array.length-1
    var target = array[start] // {1} takes the first comparison value
    while (l < r) { // {2} the left index l < the right index r
        while (l < r && array[r] >= target) {
            r-- // {3} >=targe, continue to the left for comparison
        }
        array[l] = array[r] Array [r] == array[l]; array[l] == array[l]
        while (l < r && array[l] < target) { // Array [r] = tagrget; // Array [r] = tagrget;
            l++ // {6} 
        }
        array[r] = array[l] Array [l] == array[r]; // {7} If the value >=target, the value is assigned to the position of index r
    }
    array[l] = target; Array [l] = array[r] = array[l]
    quickSort2(array, start, l - 1); // Repeat the comparison recursively
    quickSort2(array, l + 1, end); // Repeat the comparison recursively
    return array;
}
console.log(quickSort2(arr, 0, arr.length - 1)) / /,2,3,4,5,6,7 [1]
Copy the code

The complexity of the

The average time complexity is O(nlogn). In the worst case, if the array to be sorted is already sorted, the algorithm degrades to order O(n²). This can be avoided by reasonable selection of partition points. Common strategies include middle selection, random selection, and three selection.

If we pick a random partition point here, and then swap it with the last element, we can probably avoid the worst case.

Quicksort is an in-place algorithm that requires no extra space, but recursion requires space (equivalent to manually maintaining a call stack), and the overall space complexity is “O(logn)”. Equal elements may swap back and forth, and therefore not be in stable order (because of swapping).

other

# Front-end algorithm learning – algorithm complexity # Front-end required algorithm (a) : bubble sort # front-end required algorithm (two) : select sort # front-end required algorithm (three) : insert sort # front-end required algorithm (four) : merge sort

The last

Dregs a, welcome the various gods many correction, not praise, but supervision correction \

reference

# Handwritten algorithm and remember it: Quicksort (easiest to understand version)