This is the 19th day of my participation in the Genwen Challenge

Quick sort

Quicksort is also an old friend of ours from algorithm books. So merge sort has a lot in common with the backward traversal of a binary tree, but what does quicksort have in common with?

It’s a binary tree traversal! Pre-order traversal has two important features:

  • Get the root information
  • Pass information about the root to the left and right subtrees

For sorting, order is information. So what we’re going to do is we’re going to pass as much ordered information as we can to the left subarray and the right subarray.

Analysis of fast row

1. The transmission of order

In the case of quicksort, it conveys order by picking a number x and using that number, dividing the array into three parts:

  • Anything less than x is placed at the top of the array
  • The part equal to x goes in the middle of the array
  • Anything greater than x goes at the end of the array

2. Left and right subarray processing

In this case, anything less than x is the left subtree of the binary tree, and anything greater than x is the right subtree of the binary tree. The part equal to x is the root of the binary tree.

So the next thing you want to do is recursively process the left subarray and the right subarray just like the preceding traversal.

In contrast to the binary tree’s anteorder traversal, quicksort also has its own characteristics:

  • To process the root node, we need to perform the “three-way split” operation, which divides an array into three segments.
  • The left and right subintervals are dynamically generated by shards and are not fixed by Pointers like binary trees.

This can be expressed in pseudocode as follows:

Function preorder traversal/quicksort (): get the information of the root node pass the information of the root node to the left and right subtrees/left and right subarraysCopy the code

So the pre-order traversal/quicksort test points can be summarized as the following 3 points:

  • How do you divide substructures
  • Get information about the root node
  • How to pass information about the root to the left and right subtrees/left and right subarrays.

So let’s start with the three aspects shown in the figure above, and look at them in contrast to the code for binary tree traversal.

Speaking fast row

1. The division

So first let’s see how we do an array of numerators. For binary trees, subtree partitioning is natural and has been specified in data structures, such as treenode. left and treenode. right.

However, for an array, if you want to achieve the optimal efficiency, then the efficiency of cutting the array into the average half should be the highest (can be associated with the efficiency of a binary balanced tree). But quicksort doesn’t guarantee that if you pick a number, you’ll cut the array in half.

The result of segmentation is as follows:

Split array A[] into three segments using x, left subtree = [less than x] = [b, L) root = [x] = [l, I) right subtree = [greater than x] = [I, e]Copy the code

2. Recursion of subarrays

Since we’re sorting, we need to sort the left subarray and the right subarray separately. If you can remember “pre-traversal of a binary tree”, sorting subarrays should also be recursive.

PreOrder (root.left); // preOrder(root.left); preOrder(root.right);Copy the code

Quicksort is written like this:

Qsort (a, b, l); qsort(a, i, e);Copy the code

Finally, we need to consider the boundary case:

  • When b >= e, it indicates that this interval is an empty interval and there is no need to sort again.
  • When b + 1 == e, that means there’s only one element, and there’s no need to sort.

The above two boundary cases can correspond to the case when the binary tree is empty and the binary tree has only one node.

The complete code

Let’s write the code for quicksort (parsing in comments) :

Void swap(int[] A, int I, int j) {int t = A[I]; A[i] = A[j]; A[j] = t; Void qsort(int[] A, int b, int e) {void qsort(int[] A, int b, int e) { Or only one node. If (b > = e | | b + 1 > = e) {return;} / / in the middle of the array elements as x final int m = b + ((e - b) > > 1); the final int x = A, [m]. / / Int l = b, I = b, r = e; while (I <= r) {if (A[I] < x) {swap(A, l++, I++);} else if (A = = x) [I] {i++;} else {swap (A, r -, I);}} / / like A preorder traversal of binary tree, Qsort (A, b, l); qsort(A, I, e);} Void quickSort(int[] nums) {if (nums == null) return; qsort(nums, 0, nums.length);}Copy the code

Complexity analysis: Quicksort is O(NlgN) in the good case and O(N2) in the bad case.