preface

Quicksort is a widely used sorting algorithm, its time complexity is O(nlogn), many articles on the network to explain the quicksort are not quite in line with the specification, this article in the form of graphic details on quicksort, and JavaScript to achieve it, welcome interested front-end developers to read this article 😁

concept

Quicksort algorithm: First a random reference value (pivot) is selected in the sequence, and then the numbers other than the reference value are divided into “less than the reference value” and “more than the reference value” categories. Arrange them in the following form

Then, the array on both sides of the reference value is quicksort until there is only one data to the left of the reference value, the sort is complete.

The illustration example

As shown in the figure, we use quicksort to order them from smallest to largest.

Classify data according to baseline values

  • Select a base value at random, using 4 as the base value here
  • Other numbers are compared to the base value, and those less than the base value move to the left and those greater than the base value move to the right.
  • First, compare 3 with base value 4
  • 3 is less than 4, so let’s move 3 to the left
  • Next, compare 5 with the base value of 4
  • 5 is greater than 4, so we move 5 to the right
  • Repeat the above operation, and the final result is shown in the figure below.
  • The first classification is completed by inserting the reference value 4 into the sequence. Everything to the left of the base value is smaller than that, everything to the right of the base value is larger than that.

The classified data are sorted by recursive quicksort

As shown in the figure, we have classified the data according to the reference value, and divided the data into two parts: left sequence and right sequence. We performed recursive quick sorting of these two parts of data respectively to complete the overall sorting.

Quick sort right sequence

  • The sorting operation on both sides is the same as in the first step, we sort the right sequence
  • Pick a base value at random, this time 6
  • The rest of the data are compared with the base value of 6 respectively, less than the base value moves to the left, and greater than the base value moves to the right.
  • Compare data, move positions
  • As before, sort the left and right data to complete the overall sorting. At this time, we found that there was only 5 to the left of the base value, which was in the sorted state and no operation was needed.
  • There are 8, 9, and 7 left in the sequence, and we use 8 as the base value
  • When the base value is compared to other data, there is only one data on either side of the base value, so no operation is required, and the sorting is complete.
  • Going back to the last sort, since 7, 8, and 9 are sorted, so are 5, 6, 7, 8, and 9.
  • This completes the sorting to the right of the originally selected base value of 4

Quick sort left sequence

Use the same method, select base values, compare data, move positions.

As shown in the figure, the overall sorting is complete

Quick sort with JS

As the illustration example described above, we want to realize the quick sort, you must select a benchmark, then according to the benchmark data can be divided into two arrays: smaller than benchmark arrays and larger than the basic value, the smaller than benchmark data into smaller than at baseline array, the basic value greater than or equal to the array of data into the larger than the benchmark.

The above operation is recursed to the left and right of the base value, and the length of the array on either side is less than 2, the recursive operation ends.

  • Declares a function that takes an array to be sorted
  • Calculate the reference value. Since the reference value is random in the concept of quicksort, we need to use the random function to generate the reference value
  • Declares two arrays, one for holding the data divided by the base value
  • Iterating through the parameters, taking the reference value and comparing it with other elements in the array, putting the data greater than or equal to the reference value in the larger array, and putting the data less than the reference value in the smaller array.
  • Perform the above operations to recurse the data divided by the reference value respectively. When the sorted array length is less than 2, the current array is already sorted and the recursion is terminated
  • After performing quicksort, the data in their array has been sorted in order from smallest to largest. We just need to merge it with the base value, and the whole sorting work is completed

Next, let’s translate this idea into code

/ quick sort: * * * * @ param arr requires quick sort an array of * @ returns {*} [] | * * /
const quickSort = function (arr) {
    if(arr.length < 2) return arr;
    // Randomly select a reference value between 0 and arr. Length
    const pivot = Math.floor(Math.random() * arr.length)
    // Declare two arrays for storing data smaller than the base value and data larger than the base value
    let minArr = [];
    let maxArr = [];
    // Populate the array with reference values
    for(let i = 0; i < arr.length; i++){
        // If the value is greater than the baseline value, put it in maxArr
        if(arr[i] >= arr[pivot] && i ! == pivot){ maxArr.push(arr[i]); }// If the value is less than the baseline value, put it in minArr
        if(arr[i] < arr[pivot] && i ! == pivot){ minArr.push(arr[i]) } }// Call quicksort recursively on the datum arrays, then merge the arrays
    return [...quickSort(minArr), arr[pivot], ...quickSort(maxArr)];
}
Copy the code
  • Test the quicksort function we implemented above
const dataArr = [3.5.8.1.2.9.4.7.6];
console.log(quickSort(dataArr))
Copy the code

In this paper, the implementation of quicksort is fully in line with the definition of quicksort in the book, but in practical application, it is not in place, which will cause too much memory consumption, and unstable, and the sorting efficiency is low.

The optimal implementation of quicksort is three-way sorting, welcome you interested front-end developers to read my other article: sorting algorithm: Quicksort optimization => three-way quicksort understanding and implementation

Write in the last

  • The pictures used in this article are from “my first algorithm book”, if infringement, please leave a message in the comment section, the author immediately delete the relevant pictures.
  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
  • This article was first published in nuggets. Reprint is prohibited without permission 💌