preface
Since many algorithm problems in LeetCode involve some basic data structures, in order to better understand the animation of some complex problems updated later, a new series —– “Illustrated Data Structures” is launched, mainly using animation to describe common data structures and algorithms. This series includes ten kinds, heap, queue, tree, and search set, graph and so on about dozens of articles.
Quick sort
Quicksort is a sorting algorithm developed by Tony Hall. On average, order n two items and compare them (nlogn) several times. In the worst case, a comparison of TWO (N2) steps is required, but this is not common. In fact, quicksort is generally significantly faster than any other two (NLOGN) algorithms because its inner loop can be implemented efficiently on most architectures.
Quicksort uses a Divide and conquer strategy to Divide one serial (list) into two sub-lists.
Quicksort is a typical application of divide-and-conquer in sorting algorithm. Quicksort is essentially a recursive divide-and-conquer method based on bubble sort.
Algorithm steps
-
Pick an element from the sequence, called pivot;
-
Reorder the array 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 array. 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;
The bottom case of recursion is if the sequence is of size zero or one, so it’s always sorted. The algorithm always exits, though recursively, because in each iteration it puts at least one element in its last position.
Source: github.com/hustcc/JS-S…
Algorithm demo
Sort animation process explanation
-
First, you manipulate all the numbers in the sequence
-
Choose a number out of all the numbers as the base for sorting (Pivot). Pivots are usually chosen at random, and here for demonstration purposes, we choose the rightmost number as pivot
-
After pivot is selected, the leftmost number in the operation sequence is marked as the left mark and the rightmost number as the right mark
-
Move the left marker to the right
-
When the left mark reaches a number beyond pivot, the movement stops
-
In this case, 8 is greater than 6, so stop moving
-
Then move the marker on the right to the left
-
When the right mark reaches a number less than pivot, the movement stops
-
In this case, 4 is greater than 6, so stop moving
-
When the left and right tags stop, change the number of tags
-
Thus, the left marker is used to find a number greater than Pivot, and the right marker is used to find a number less than Pivot
-
By swapping numbers, a collection of numbers smaller than Pivot can be collected on the left side of the array and larger than Pivot on the right
-
After the exchange, continue to move the left tag
-
In this case, 9 is greater than 6, so stop moving
-
Then move the marker on the right to the left
-
The right tag also stops moving when it hits the left tag
-
If the left and right marks stop, and both are in the same position, swap this number with the pivot number
-
This completes the first operation
-
Anything less than 6 is to the left of 6, anything greater than 6 is to the right of 6
-
And then recursively do the same thing to both parts of the partition
-
Complete quicksort
Code implementation
In order to better let readers use their familiar programming language to understand animation, the author will post a variety of programming language reference code, code all from the Internet.
C++ code implementation
Java code implementation
Python code implementation
JavaScript code implementation
If you’re an iOS developer, you can go to GitHub at github.com/MisterBooo/… Get more intuitive debug run source code.
You can pay attention to the public number five minutes learning algorithm for more sorting content.
Welcome to:
