Follow-up: Quick Sort Implementation and Applications

In the previous article Detailed Explanation of Merge Sort Algorithm, the principles and applications of the merge sort algorithm were described from the perspective of binary trees. Many readers found it ingenious. So, I will capitalize on this momentum and today, continue to explain the principles and applications of the quicksort algorithm using the perspective of binary trees.

QuickSort Algorithm Approach

First, let's take a look at the code framework of quicksort:

void sort(int[] nums, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    // partition the nums[lo..hi]
    // such that nums[lo..p-1] <= nums[p] < nums[p+1..hi]
    int p = partition(nums, lo, hi);
    // recursively partition the left and right subarrays
    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

void sort(int nums[], int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    // partition the nums[lo..hi]
    // such that nums[lo..p-1] <= nums[p] < nums[p+1..hi]
    int p = partition(nums, lo, hi);
    // recursively partition the left and right subarrays
    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

def sort(nums: List[int], lo: int, hi: int):
    if lo >= hi:
        return
    # partition the nums[lo..hi]
    # such that nums[lo..p-1] <= nums[p] < nums[p+1..hi]
    p = partition(nums, lo, hi)
    # recursively partition the left and right subarrays
    sort(nums, lo, p - 1)
    sort(nums, p + 1, hi)

func sort(nums []int, lo int, hi int) {
    if lo >= hi {
        return
    }
    // partition the nums[lo..hi]
    // such that nums[lo..p-1] <= nums[p] < nums[p+1..hi]
    p := partition(nums, lo, hi)
    // recursively partition the left and right subarrays
    sort(nums, lo, p-1)
    sort(nums, p+1, hi)
}

var sort = function(nums, lo, hi) {
    if (lo >= hi) {
        return;
    }
    // partition the nums[lo..hi]
    // make nums[lo..p-1] <= nums[p] < nums[p+1..hi]
    var p = partition(nums, lo, hi);
    // recursively partition the left and right subarrays
    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
};

In fact, if you compare them, you'll find that quicksort is essentially a preorder traversal of a binary tree:

// Binary tree traversal framework
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // ***** Pre-order position *****
    print(root.val);
    // *******************
    traverse(root.left);
    traverse(root.right);
}

// Binary tree traversal framework
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // ***** Pre-order position *****
    cout << root->val << endl;
    // *******************
    traverse(root->left);
    traverse(root->right);
}

# Binary tree traversal framework
def traverse(root: TreeNode):
    if not root:
        return
    # Pre-order position
    print(root.val)
    traverse(root.left)
    traverse(root.right)

// Binary tree traversal framework
func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // Pre-order position
    fmt.Println(root.Val)
    traverse(root.Left)
    traverse(root.Right)
}

// Binary tree traversal framework
var traverse = function(root) {
    if (root === null) {
        return;
    }
    // ***** Pre-order position *****
    console.log(root.val);
    // *******************
    traverse(root.left);
    traverse(root.right);
};

Additionally, in the previous article Detailed Explanation of Merge Sort, merge sort was summarized in one sentence: first sort the left half of the array, then sort the right half of the array, and finally merge the two halves.

I also posed a question asking you to summarize quicksort in one sentence. Here is my answer:

Quicksort sorts one element first, and then sorts the remaining elements.

Why is this? Let me explain.

The core of quicksort is undoubtedly the partition function. The purpose of the partition function is to find a pivot point p in nums[lo..hi], rearranging elements so that nums[lo..p-1] are all less than or equal to nums[p], and nums[p+1..hi] are all greater than nums[p]:

Elements to the left of this pivot are smaller, and elements to the right are larger. What does this mean? It means the pivot element is already in its correct position.

Therefore, what the partition function essentially does is sort the nums[p] element.

Once one element is sorted, what's next? You simply sort the remaining elements.

What are the remaining elements? There's a chunk on the left and a chunk on the right. Go ahead and recursively sort these subarrays using the partition function.

From the perspective of a binary tree, we can understand the subarray nums[lo..hi] as the values at the nodes of a binary tree, and the sort function as the traversal function of the binary tree.

Referencing the pre-order traversal of a binary tree, the operation of quicksort is illustrated in the following GIF: