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.

The previous article was a 5 line implementation version. This is the in situ sorting algorithm.

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 big part of merge is how to merge, the big part of quicksort is how to divide.

In the figure above, we split the array into three parts by dividing the last element, 4. Except for the cut-off point, the left subparts are all less than or equal to 4, and the right subparts are all greater than 4, and they can be sorted recursively. Because you sort in place (you don’t need extra space), you don’t need the merge operation.

Among them, normalization is relatively easy, the core of the algorithm is: how to divide the array into three according to the dividing point?

Tutorials can be implemented in different ways, but here’s one that’s easiest to understand.

Here’s how you do it: you pick the last element as the cut-off point, and then you go through the array looking for anything less than or equal to the cut-off point, and then you swap it in front of the array. Such as:

In the figure above, we find elements less than or equal to 4 in order, 1, 2, 3, 4. Then swap with the first four elements of the array. The result is split into three.

Is it an easy line of thought to follow? Quick platoon is not hard to learn.

We use JS to implement a:

let array = [7.1.6.5.3.2.4]
let j = 0
let pivot = array[array.length - 1]
for (let i = 0; i < array.length; i++) {
  if (array[i] <= pivot) {
    swap(array, i, j++)
  }
}
console.log(array) // [1, 3, 2, 4, 7, 6, 5]
Copy the code

The swap function encapsulates how two elements are swapped:

function swap(array, i, j) {
  [array[i], array[j]] = [array[j], array[i]]
}
Copy the code

Further encapsulated as a function:

function partition(array, start, end) {
  let j = start
  let pivot = array[end]
  for (let i = start; i <= end; i++) {
    if (array[i] <= pivot) {
      swap(array, i, j++)
    }
  }
  return j - 1
}
Copy the code

Start and end represent the start and end indices of an array. J-1 is the position of the cut-off point.

Then we need to recursively deal with the left and right subparts.

Recursion, it doesn’t follow linear thinking, but it’s really not 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 quicksort 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

Easily translated into code:

function quickSort(array, start = 0, end = array.length - 1) {
  let pivotIndex = partition(array, start, end)
  quickSort(array, start, pivotIndex - 1)
  quickSort(array, pivotIndex + 1, end)
  return array
}
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 (end - start < 1) return array
Copy the code

So far, the principles and implementation of quicksort have been covered.

The algorithm of fast sorting mainly lies in the partition function implementation, the implementation of different tutorials are different, this need to pay attention to.

The average time complexity is O(nlogn). In the worst case, if the array is already sorted, the algorithm degrades to order O(n^2). 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 swap it with the last element, we can probably avoid the worst case scenario. See the full code: codepen.

To summarize, 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). 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
  • “Handwriting algorithms and Memorizing them: QuickSort (Simple 5 Lines of Code)”