Follow-up: Quick Sort Implementation and Applications

In the last article Merge Sort Explained, we used the idea of binary trees to explain merge sort and how it works. Many readers liked it, so today I will keep using the binary tree view to explain how quick sort works.

How Quick Sort Works

First, let's look at the main code framework for quick sort:

void sort(int[] nums, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    // ****** pre-order position ******
    // partition the nums[lo..hi], put nums[p] in the right position
    // 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;
    }
    // ****** pre-order position ******
    // partition the nums[lo..hi], put nums[p] in the right position
    // 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
    # ****** pre-order position ******
    # partition the nums[lo..hi], put nums[p] in the right position
    # 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
    }
    // ****** pre-order position ******
    // partition the nums[lo..hi], put nums[p] in the right position
    // 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;
    }
    // ****** pre-order position ******
    // partition the nums[lo..hi], put nums[p] in the right position
    // 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);
};

If you compare, you will see that quick sort is very much like 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);
};

Also, the article Merge Sort Explained used one sentence to sum up merge sort: first sort the left half of the array, then sort the right half, and then merge them.

I also asked a question: can you use one sentence to describe quick sort? Here is my answer:

Quick sort first puts one element in place, then sorts the rest of the elements.

Why do I say this? Let me explain.

The key part of quick sort is the partition function. The job of partition is to find a split point p in nums[lo..hi], and swap 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]:

All elements on the left are smaller, all elements on the right are bigger. What does this mean? It means nums[p] is now in its correct position.

So, what does the partition function do? It puts nums[p] in the right place.

After one element is in place, what next? Just sort the rest.

What are the rest? The ones on the left and the ones on the right. Use recursion on these subarrays, use partition to sort them.

From the view of a binary tree, the subarray nums[lo..hi] can be seen as the value of a tree node, and the sort function as the traverse function of the tree.

Looking at quick sort as a preorder traversal, the process looks like this GIF:

Quick Sort Code Implementation

Complexity Analysis and Other Key Points

Quick Select Algorithm