This is the third day of my participation in the First Challenge 2022

Quicksort, short for quicksort. Quicksort is the most widely used of all sorting algorithms. Next we’ll talk about how a classic quicksort is implemented.

Train of thought

The core idea of fast platoon is divide and conquer.

The so-called divide and rule, is the meaning of divide and rule, the original problem split into a number of smaller problems, these sub-problems can continue to split, is the so-called doll, until the small scale to directly solve. By solving the sub-problem, the parent problem is completed and the original problem is finally solved.

The idea of divide-and-conquer is implemented recursively. Recursion refers to a form of calling a function during the execution of a function. When the recursion reaches a certain level, the logic to exit recursion will be triggered.

Divide and conquer is the idea, recursion is the method, do not confuse the two.

Partition (); partition ();

For the supplied array, we randomly pick one of the array elements and find a reference value (Pivot), or intermediate value. Then partition the array into two parts, the left part less than or equal to pivot, and the right part greater than pivot.

Then our divide-and-conquer, or recursion, continues to do the same thing for the left and the right, until the interval is less than or equal to 1.

implementation

Let’s look at the code implementation first.

function quickSort(arr) {
  partition(arr, 0, arr.length - 1);
  return arr;
}

function partition(arr, lo, hi) {
  if (lo >= hi) return; // Recursively jump out of the condition, can be directly solved by the subproblem
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) {
      swap(arr, i, j) / / exchange
      i++;
    }
  }
  swap(arr, i, hi);
  partition(arr, lo, i - 1);
  partition(arr, i + 1, hi);
}

function swap(arr, i, j) {
  let tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}
Copy the code

The core algorithm is the partition algorithm. The algorithm is cleverly implemented to sort in place (without using additional data structures).

A partition takes an array and an index interval [LO, hi] to be partitioned. Note that this is a closed interval.

Here we maintain an I pointer and a j pointer. The j pointer increments by one with each iteration. This interval represents the interval less than or equal to pivot, and this interval is dynamic because I changes.

In traversal, if the current value is less than or equal to pivot, the value is placed in the range [lo, I]. The implementation is to swap the array elements on I and j and increment I by one.

It is important to note that the traversal must not have j == hi, and that pivot needs to be moved to the center at the end of the traversal. Let’s say j ≤ hi, because the element I corresponds to is greater than or equal to pivot, and if it’s greater than pivot, I and pivot won’t swap.

Why is quicksort the most widely used?

The average time complexity of fast sorting is O(n * logn), which is much better than the time complexity of bubble sort and insert sort, which are O(n^2). The derivation is a little bit complicated, so I won’t expand it here.

Merge sort is also order n logn. In extreme cases, the time decays to O(n^2).

Merge sort doesn’t. Merge sort is actually better in terms of time complexity.

However, quicksort can save memory space by in-place sorting, that is, the space complexity is O(1), while the space complexity of merge sort is O(n).

But quicksort also has a serious drawback, because quicksort is an unstable sort because of swapping elements. When you sort, the same values might be in a different relative order than the same values, but sorting arrays is fine, but when you sort objects by ID, it might confuse us.

Some strange quicksort implementations

I saw this realization on the Internet.

var quickSort = function (arr) {
  if (arr.length <= 1) { return arr; }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1) [0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else{ right.push(arr[i]); }}return quickSort(left).concat([pivot], quickSort(right));
};
Copy the code

This implementation is ideologically correct and divide-and-conquer, but the fatal problem is that instead of sorting in place, it requires additional arrays. It’s best not to include this implementation in your interview, although it may seem shorter.

The idea of quick sorting is not complicated, but the implementation uses a lot of variables, and it still takes time for beginners to understand.