Quick sort

Quicksort is an improvement of Bubble Sort algorithm.

Sorting process

The quicksort algorithm realizes sorting by comparing and swapping several times, and its sorting process is as follows:

  1. You start by setting a boundary that divides the array into left and right parts.
  2. Collect data that is greater than or equal to the boundary to the right of the array, and data that is less than the boundary to the left of the array. In this case, everything on the left is less than or equal to the boundary, and everything on the right is greater than or equal to the boundary.
  3. Then, the left and right data can be sorted independently. For the array data on the left, you can take a boundary value to divide the part of the data into left and right parts, and also place a smaller value on the left and a larger value on the right. You can do the same for the array data on the right.
  4. As you repeat the process, you can see that this is a recursive definition. After recursively ordering the left, recursively ordering the right. When the sorting of the left and right parts of the data is completed, the sorting of the entire array is completed.

advantage

An algorithm with strong comprehensive ability, which performs well in most cases (when sorting near-sorted arrays, it is inferior to insertion sort)

Quick sort problems and optimizations

Optimization of 1

  • Problem: Sort nearly sorted arrays is inefficient.
  • Reason: design, initial boundary value set to the first element of child series, in ordinary in the array, there will be a problem, but for a better array is sorted, this leads to the process of sorting, almost all of the elements are assigned to the right, so it can not embody the quick sort of “divide and conquer” effect, the quick sort will be degraded to O (N2) algorithm.
  • Optimization: Boundary value is selected by random method. While the worst-case scenario is still slow, the probability of a worst-case scenario has dropped to close to zero.

Optimization of 2

  • Problem: Sorting highly repetitive arrays is inefficient.
  • Reason: when there are many elements and the boundary value elements are equal, it will also lead to the phenomenon that one side is long and the other side is short, and the algorithm will degenerate.
  • Optimization: add a pointer to the set of elements equal to the demarcation value in the middle, this is the middle part is equivalent to the sorted, the next step is only less than and greater than the demarcation value of the elements can be sorted.

Demo animation

Sort a regular array

View slow demos, code, test cases

Sort an almost sorted array

View slow demos, code, test cases

Sort highly repetitive arrays

View slow demos, code, test cases