preface

Quicksort is probably the most famous algorithm in sorting, and probably the most widely used. It is popular because it is simple to implement, works well with a variety of data, and is generally faster than other sorting algorithms.

Fast row principle

Quicksort is an improvement over bubble sort, which is fast because a swap can change multiple inversions, whereas bubble sort can change only one.

The basic idea of quicksort is to divide the sorted data into two parts in a single sort, with one part of the data smaller than the other. Then we continue to do a quick sort of the two pieces of data. Is the embodiment of the idea of divide and rule.

Now let’s use a legend to see a sort

The process is as follows:

  1. Select array A [LO] as the shard element, and let I = LO, j = hi, that is, corresponding lo, hi positions
  2. The I pointer scans from left to right and pauses when it meets a number >v; The j pointer scans from right to left and pauses when it meets a number

    = j.
  3. When the 2 process ends, j points to a number less than the shard element and is switched. At this point, the shard element is in the final position, the elements on the left of the shard element are all smaller than the shard element, and the elements on the right are all larger than the shard element
  4. Sort (array, lo, j-1); sort(array, lo, j-1) Sort (array, j + 1, hi). Until the recursion ends

Code implementation

Core code sort and partition, sort for recursive call, partition for shard

  sort(array, lo, hi) {
    if(hi <= lo ){
      return ;
    }
    const j = this.partition(array, lo, hi);
    this.sort(array, lo, j - 1);
    this.sort(array, j + 1, hi);
  }
  partition(array, lo, hi){
    let i = lo;
    let j = hi + 1;
    const ele = array[lo];// Shards elements
    while(true) {while(this.less(array[++i], ele)){// Scan left to right
        if(i === hi){
          break; }}while(this.less(ele, array[--j])){// Scan right to left
        if(j === lo){
          break; }}if(i >= j){
        break;
      }
      this.exch(array, i ,j);// Swap left and right elements
    }
    this.exch(array, lo, j);// Split the element swap
    return j;
  }

Copy the code

CodePen open

The performance characteristics of

Main advantages:

  • Implement a simple
  • It is generally much faster than other sorting algorithms
  • The sorting time of an array of length N is NlgN
  • Inner loops are shorter than most sorting algorithms

Main disadvantages:

  • Fragile, which can result in extremely poor performance when shard is unbalanced. Such as reverse order to ascending order

conclusion

The above quicksort is the most basic version. There is a lot of room for improvement for different scenarios, such as:

  • For small arrays you can switch to insert sort in quicksort
  • For an array with a large number of repeating elements, such as birthday or gender, you can split the array into three parts that correspond to elements less than, equal to, or greater than the shard element

The above content is also mainly learned from “Algorithm (4th edition)” book, interested students can refer to.

The resources

“Algorithm (4th Edition)” Quicksort algorithm in detail (principle, implementation and time complexity)