Quick Sort

The basic idea of quick sorting is that the records to be sorted are separated into two independent parts through one sort. The keywords of one part of the records are smaller than those of the other part. Then the two parts of the records can be sorted separately to achieve the entire sequence.

Algorithm description

Quicksort uses divide-and-conquer to divide a list into two sub-lists. The specific algorithm is described as follows:

• Picking out an element from the sequence, called a "pivot";
• Reorder the sequence so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition exits, the benchmark is in the middle of the sequence. This is called a partition operation;
• Recursively sorts subsequences of elements less than the base value and subsequences of elements greater than the base value.

Animation

Code demo

/**
 * @description: Sets the base value pivot
 * @param {Array} list
 * @param {number} left
 * @param {number} right
 * @return {number} index
 */
const partition = (list: number[] = [], left: number, right: number) => {
  const pivot = left;
  let index = pivot + 1;
  for (let i = index; i <= right; i++) {
    if (list[i] < list[pivot]) {
      if (list[i] !== list[index]) {
        list[i] = list[i] ^ list[index];
        list[index] = list[i] ^ list[index];
        list[i] = list[i] ^ list[index];
      }
      index++;
    }
  }
  if (list[index - 1] !== list[pivot]) {
    list[index - 1] = list[index - 1] ^ list[pivot];
    list[pivot] = list[index - 1] ^ list[pivot];
    list[index - 1] = list[index - 1] ^ list[pivot];
  }
  return index - 1;
};
/**
 * @description: Continuously partition, set the reference value
 * @param {Array} list
 * @param {number} left
 * @param {number} right
 * @return {Array}
 */
const combine = (list: number[], left: number, right: number) => {
  if (left < right) {
    const partitionIndex: number = partition(list, left, right);
    combine(list, partitionIndex + 1, right);
    combine(list, left, partitionIndex - 1);
  }
  return list;
};
/**
 * @description: Quick sort
 * @param {Array} list
 * @return {Array}
 */
const quick = (list: number[] = []): number[] => {
  const size = list.length;
  return combine(list, 0, size - 1);
};

Algorithm analysis

Quicksort's average time complexity is O(n log n), but the worst case is O(n²) when every pivot choice splits the list as unevenly as possible. This implementation always picks the leftmost element as the pivot (partition's pivot = left), so — unlike a randomized-pivot quicksort — an already-sorted or reverse-sorted input triggers exactly that worst case. Quicksort is not stable, and while it sorts in place, the recursive calls in combine use O(log n) stack space on average, growing to O(n) in the worst case.