Have you ever had a classic algorithm that you thought was clear in the class, but forgot after a while?

This series of articles attempts to address that question.

Read up on the sorting algorithms, read up on their names, and they’re all very aptly named.

For example, quicksort, a fast word can show its value, so it is the most used.

Because it is more difficult, this series will cover it in two articles.

This is a simple implementation of the version, and merge sort do contrast, find out the overall idea of fast row. The next article is the in situ sorting algorithm that is common in various tutorials.

Quicksort is named for its performance, but it’s hard to make sense of it.

So, I gave it a new name: classified sorting.

Like merge algorithm, partition algorithm is also divide and conquer algorithm, pay attention to partition, return and union. The former focuses on how to merge, while the latter focuses on how to divide.

In the figure above, we split the array into three parts by dividing the last element, 4. The left subparts are all less than or equal to 4, and the right subparts are all greater than 4, so they can recursively sort further, and then merge these three parts.

The core of this algorithm is: how to divide the array into three according to the dividing point?

This is very easy for us JSer to do using the filter:

let pivot = array[array.length - 1]
let left = array.filter((v, i) = >v <= pivot && i ! = array.length- 1)
let right = array.filter(v= > v > pivot)
Copy the code

The left part excludes the cut-off element, so it cannot be the last.

Now that the core problem is solved, let’s look at union and return.

To concatenate three arrays, there are apis in JS (such as concat). Here we simply use the expansion operator:

let result = [...left, pivot, ...right]
Copy the code

As for recursion, it’s not linear, but it’s not really that hard.

As long as there are recursive steps (recursive formulas), it is easy to translate into code.

Let’s recall the steps of the segmentation algorithm:

  1. The array is divided into three parts: left, pivot, and right, so that left<=pivot, right>pivot
  2. Recursive left
  3. Recursively process right
  4. Combine the three results

Easily translated into code:

function quickSort(array) {
  let pivot = array[array.length - 1]
  let left = array.filter((v, i) = >v <= pivot && i ! = array.length- 1)
  let right = array.filter(v= > v > pivot)
  return [...quickSort(left), pivot, ...quickSort(right)]
}
Copy the code

Recursion is a call to itself that cannot go on indefinitely, so there needs to be a recursive exit (initial conditions).

Its recursive exit is that when the number of elements in the array is less than 2, it is sorted and no more recursive calls are required.

So you need to add code in front:

if (array.length < 2) return array
Copy the code

See the full code: codepen.

So far, we’ve implemented a simple version of quicksort, as opposed to merge sort.

To summarize, this version of quicksort requires extra space for each recursive call, order n complexity, and is not local sort. Speaking of spatial complexity, recursion also requires space (equivalent to manually maintaining a call stack), so the overall spatial complexity is O(nlogn). Equal elements do not swap back and forth, so they are in stable order (this is related to the fact that we chose the last element as the cut-off point). The time complexity is O(nlogn).

Quick sort, to be able to hand out minutes, is the need to master the sorting principle. The key is how to split the array into three according to the cut-off point. As for recursion, it is easy to write as long as the recursive steps and the exit are clear, and there is no need to memorize.

Hope to help, the end of this article.


Articles in this series have been published:

  • Handwriting Algorithms and Remember it: Bubbling Sort
  • Handwriting Algorithms and Remembering them: Sorting by Choice
  • Handwriting Algorithms and Remembering them: Insertion Sort
  • Handwriting algorithm and Remember it: Merge Sort