This is the 18th day of my participation in Gwen Challenge

What is quicksort

Like merge sort, quicksort uses a divide-and-conquer algorithm.

Quicksort is an algorithm evolved from bubble sort, but the performance of quicksort is far better than bubble sort.

Quicksort basic steps:

  1. Quicksort selects a value from the array as the base element (the selection and use of base elements are described in “Related Concepts”)
  2. And create a two-pointer reference (left and right, described in “Related Concepts”).
  3. Move the left pointer until it finds a value larger than the base element, then move the right pointer until it finds a value smaller than the base element, then swap them, and repeat the process until the left pointer exceeds the right. All values less than the base element are to the left of the base element, and all values greater than the base element are to the right.
  4. The algorithm performs the same steps on the partitioned small array (subarray of values smaller than the primary element, and subarray of values larger than the primary element) until the array is completely sorted.

Relevant concepts

Base element

Pivot picks a base element in each turn, makes it the center of divide-and-conquer, and moves the larger element to one side of the sequence and the smaller element to the other, splitting the sequence into two parts.

How do you choose a base element?

There are many ways to select the base element, such as selecting the first element of the sequence, the element in the middle of the sequence, or even selecting an element randomly.

This example uses the element in the middle of the sequence as the base element.

The selection of base elements is not absolutely good or bad, but depends on the selection of base elements, the probability of selecting the maximum or minimum value of the sequence, resulting in the change of time complexity.

The average time of quicksort is O (nlogn), and the worst case is O (n^2).

Pointer to the left

Quicksort uses the two-pointer method, which is used to scan elements before they are swapped. It is divided into left pointer and right pointer.

The left pointer initially points to the first element in the sequence, and the goal of the left pointer is to find an element larger than the base element.

Pointer to the right

Quicksort uses the two-pointer method, which is used to scan elements before they are swapped. It is divided into left pointer and right pointer.

The right pointer starts at the last element in the sequence, and the goal is to find an element smaller than the base element.

Graphical quicksort

Suppose we were to sort such a sequence

Select the rightmost number as the base element (this is just one of many ways to select a base element)

And creates a two-pointer reference, with the left pointer initially pointing to the first element of the array and the right pointer initially pointing to the last element of the array.

Move the left pointer until it finds a value greater than the base element, at which point it finds 8

Move the right pointer until it finds a value smaller than the base element, at which point it finds 4

And then we swap them, so we swap 8’s and 4’s

Repeat the same steps and continue moving from the left tag until you find a value greater than the base element, at which point you find 9

Moving from the right tag, but no left and right tags touching each other, will stop moving and swap the number with the base element.

All values less than the base element are to the left of the base element, and all values greater than the base element are to the right.

Partition the elements before the base element into the left subarray [3,5,4,1,2], and the elements after the base element into the right subarray [8,7,9].

In this case, the left subarray is the element before 2, and the right subarray is the element after 2 and before 6, that is, [4,3,5].

Because there is only one digit 1 on the left, the sorting is considered complete and no operation is required. Now operate on the right subarray [4,3,5].

Repeat the same process until all numbers are sorted.

After operating on the outermost left subarray, continue with the same operation on the right subarray.

Finally, all the numbers are sorted.

Quicksort animation illustration

Code implementation

// A constant object for comparison (to keep code elegant)
export const Compare = {
  LESS_THAN: -1.// If the first element is less than the second, it returns -1
  BIGGER_THAN: 1.If the first element is greater than the second, it returns 1
  EQUALS: 0 // If the element has the same reference, it returns 0
};
// Compare the methods used
export function defaultCompare(a, b) {
  // If the element has the same reference, it returns 0
  if (a === b) {
    return Compare.EQUALS;
  }
  // If the first element is less than the second, it returns -1, otherwise it returns 1
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
/** * swap function *@param {*} Array passes in the array to swap (in this case the heap) *@param {*} A passes in the node a * to be swapped@param {*} B passes in the node b */ to be swapped
 export function swap(array, a, b) {
  // ES5
  /* const temp = array[a]; // To swap two values in an array, we need an auxiliary variable to copy the first element to swap array[a] = array[b]; // Then assign the second element to the position of the first element array[b] = temp; * / // Finally, the copied value of the first element is overwritten to the position of the second element
  / / ES6 writing (poorly) https://bugzilla.mozilla.org/show_bug.cgi?id=1177319
  [array[a], array[b]] = [array[b], array[a]];
}
There are several ways to select a base element. The most common way is to select the value in the middle of the array@param {array} Array Array to be sorted *@param {array} Left Left low pointer *@param {array} Right right high pointer *@param {function} CompareFn // Compare with defaultCompare * by default@returns {array} Returns the sorted array */
function partition(array, left, right, compareFn) {
  const pivot = array[Math.floor((right + left) / 2)]; // We choose the intermediate value as the base element
  let i = left; // left pointer initialized to the first element of the array;
  let j = right;

  while (i <= j) { // As long as the left and right Pointers are not interleaved, the partition operation is performed.
    while (compareFn(array[i], pivot) === Compare.LESS_THAN) { // First, move the left pointer until an element larger than the base element is found
      i++;
    }
    while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) { // For the right pointer, we do the same thing, moving the right pointer until we find an element smaller than the base element
      j--;
    }
    if (i <= j) { // When the left pointer is larger than the base element and the right pointer is smaller than the base element, and the left index is not larger than the right index (I <= j), the left item is larger than the right item (value comparison).
      swap(array, i, j); // We swap them
      // Then move the two Pointers and repeat the processi++; j--; }}return i; Return the index of the left pointer at the end of the partition operation
}
/** * Internal method of quicksort *@param {array} Array Array to be sorted *@param {array} Left Left low pointer *@param {array} Right right high pointer *@param {function} CompareFn // Compare with defaultCompare * by default@returns {array} Returns the sorted array */
function quick(array, left, right, compareFn) {
  let index; // The index variable helps us separate subarrays into smaller and larger arrays.
  if (array.length > 1) { // If the length of the array is greater than 1 (because an array with only one element must be sorted)
    index = partition(array, left, right, compareFn); // We will partition the stator array (the first call is for the entire array) to get index
    if (left < index - 1) { // If the subarray has elements with smaller values
      quick(array, left, index - 1, compareFn); // Repeat the process for the array
    }
    // The same is true for subarrays with large values
    if (index < right) {  // If there are subarrays with large values
      quick(array, index, right, compareFn); // We will also repeat the quicksort process}}return array;
}
/** * quicksort *@param {array} Array Array to be sorted *@param {function} CompareFn // Compare with defaultCompare * by default@returns {array} Returns the sorted array */
export function quickSort(array, compareFn = defaultCompare) {
  return quick(array, 0, array.length - 1, compareFn);
}
Copy the code