Quick Sort and Binary Tree Preorder
Prerequisite Knowledge
Before reading this article, you should first learn:
Summary in One Sentence
The core idea of quicksort is best understood in conjunction with preorder traversal of binary trees: place an element in its correct position during the preorder traversal of a binary tree, and then recursively sort the remaining elements.
You can open this visualization panel, click the full-screen button let p = ... section of the code to visually observe the recursive process and sorting effect of quicksort:
Does this summary sound confusing to beginners? Why is array sorting related to binary trees?
This is because computer thinking is different from human thinking.
Typically, when a person wants to sort an array, they maintain a sortedIndex, ensuring [0, sortedIndex) is sorted, and gradually move the sortedIndex right until the whole array is sorted. This process involves various challenges, as described in our discussions on Selection Sort, Bubble Sort, Insertion Sort, and Shell Sort.
However, the more efficient an algorithm is, the closer it is to computer thinking, making it harder for the untrained to understand. After learning the basic sorting algorithms, you might notice that the more intuitive and derivable sorting algorithms have a complexity of , whereas those breaking the barrier seem beyond human conception.
If someone casually says: "Sorting an array is simple, just sort one element and then sort the remaining elements to sort the whole array," they might as well be an extraterrestrial agent from the Trisolaran world. 😃