1. Background
Suppose that in a program of The First Lesson of The New Semester in a parallel time and space, CCTV invited a total of 10 guests who are currently working or have worked in CCTV to participate in the chorus of singing the Motherland. In order to consider the chorus effect, the host needs to arrange the seats according to the height of the guests. First of all, the host invites 10 guests onto the stage. The initial relative positions of the guests are shown in the figure below:
The first step: the host please sit a number of Ms. Zhu Xun out; Staff A should stand in front of seat 1 and staff B should stand in front of seat 10, as shown below:
All height information in this article is not real data. Any similarity is purely coincidental), when work researchers found that B LangYongChun Mr Height is greater than the ms Zhu Xun height, so the staff B to left, then walk to the front of the seat number 9 ask ms sisi found that don’t meet, always go to the left, until you find ms OuYangXiaDan height less than the height of Zhu Xun lady, so the host seat OuYangXiaDan lady to the front of the no. 1 seat waiting for, And ask staff A to move A seat to the right, as shown in the picture below:
Step 6: The host found that there were A lot of seats on the right of Ms. Zhu Xun, so she asked Ms. Dong Qing to get out of the line, and asked the staff member A to stand in front of seat 3, and asked the staff member B to stand in front of Mr. Lang Yongchun. As shown below:
Step 20: The host found that there were two guests on the right of Ms. Wang Bingbing who were not seated. The operation steps here are similar to steps 18 and 19, which will not be described here.
Step 21: The host confirms that all the guests have taken their seats, and the staff A and B leave. At this moment, the audience friends find that our guests have been ranked from seat 1 to seat 10 according to their height, as shown in the picture:
2. How quicksort works
In this process, the host uses the method of quicksort to determine the position order of the guests.
(1) First set a boundary value (also called pivot) by which the array is divided into left and right parts.
(2) Collect the data greater than or equal to the boundary value to the right of the array, and the data less than the boundary value to the left of the array. At this point, each element in the left part is less than or equal to the boundary value, and each element in the right part is greater than or equal to the boundary value.
(3) Then, the data on the left and right can be sorted independently. For the left side of the array, you can take a boundary value and divide that part of the data into left and right parts, again placing a smaller value on the left and a larger value on the right. The array data on the right can be treated similarly.
(4) Repeat the above process, it can be seen that this is a recursive definition. After recursively ordering the left side, recursively ordering the right side. When the sorting of the left and right parts of the data is complete, the sorting of the entire array is complete.
2.3 Code Implementation (using JavaScript)
function _quickSort(arr, left, right) {
/* If there is only one guest (or no guest) who has not yet taken a seat, just ask the guest to take the seat */
if (left >= right) {
return
}
/* Let the first guest in the current sorting sequence go first, leaving the current position */
let pivot = arr[left]
/* Worker A needs the starting position of the unsorted sequence of the station */
let i = left;
/* Worker B needs the end position of the unsorted sequence of the station */
let j = right;
/* If worker A and worker B have not yet met, the loop continues */
while (i < j) {
/* If no guest is shorter than the guest who is the main element and staff B has not met staff A */
while (i < j && pivot < arr[j]) {
/* Worker B looks left */
j--
}
/* If worker B has not met worker A yet, it means that the previous while loop has found the guest whose height is less than that of the principal guest and thus exits */
if (i < j) {
/* Put the present guest in the position of the present guest (vacancy), because the current position has been processed, because the current position of the staff has been processed, so we need to ask the staff A to move one position to the right */
arr[i++] = arr[j]
}
/* If no guest is taller than the guest, and staff A has not yet met staff B */
while (i < j && pivot > arr[i]) {
/* Worker B looks to the right */
i++
}
/* If worker A has not met worker B yet, it means that the previous while loop has found the height of the guest is greater than that of the principal guest and thus exits */
if (i < j) {
/* Put the guest currently found to the position where the empty seat (the guest with lower height in the back has been moved to the front) is, because the current position of staff B has been processed, so staff B needs to move one position to the left */
arr[j--] = arr[i]
}
}
/* At this moment, the guest on the left of the empty seat must be shorter than the main element, and the guest on the right must be taller than the main element, so directly sit down as the main element guest */
arr[i] = pivot
// Sort the guests to the left of the main element by this rule
_quickSort(arr, left, i - 1)
// Order the guests to the right of the main element by this rule
_quickSort(arr, i + 1, right)
}
/** The complex _quickSort function */ is not exposed directly to the outside world in order to have a simple interface form
function quickSort(arr) {
return Array.isArray(arr) ? _quickSort(arr, 0, arr.length - 1) : arr
}
Copy the code3, advanced
In the example of the host arranging guest seats, we found that our quicksort was not so “fast”, because our pivot elements were too “sidelined” in the first few times of sorting, which caused us to divide at one time, and not many elements were moved.
Wouldn’t it be nice if we got exactly the middle element every time?
Another problem is that quicksort is sorted recursively, and every time you recurse, the function gets pushed, which means you consume a lot of storage. Guest seat is arranged in the host of the case, we have emerged only one or two elements to row for several times, but still have to use recursive this embarrassing scene, which makes the quick sort of our “slow”, then, we introduce a strategy again, when the element is less, we can directly use simple sort by sort
Therefore, based on the above analysis, there is an advanced ternary value method to improve it. The code implementation is as follows:
/** * defines a direct insert sort method. The direct insert sort method is different from normal insert sort because it sorts on a fragment of the array, so it needs to introduce an offset argument *@param {Array} Arr Array to be sorted *@param {Number} Offset Indicates the initial offset *@param {Number} Length Indicates the total length of the fragment to be sorted */
function _insertionSort(arr, offset, length) {
let temp, i;
for (let p = 1 + offset; p < offset + length; p++) {
temp = arr[p];
for (i = p; i >= 1 && temp < arr[i - 1]; i--) {
arr[i] = arr[i - 1]; } arr[i] = temp; }}/** * defines the exchange function */
function _swap(arr, posA, posB) {
let temp = arr[posA]
arr[posA] = arr[posB]
arr[posB] = temp
}
/** * defines the method */ in ternary fetches
function _mediant(arr, left, right) {
let center = Math.floor((left + right) / 2)
if (arr[left] > arr[center]) {
_swap(arr, left, center)
}
if (arr[left] > arr[right]) {
_swap(arr, left, right)
}
if (arr[center] > arr[right]) {
_swap(arr, center, right)
}
// Hide the middle element before the last element
_swap(arr, center, right - 1)
// return the middle value as the primary
return arr[right - 1]}function _quickSort(arr, left, right) {
let len = right - left + 1
In this example, if there are less than 5 elements, use direct insert sort, otherwise use quicksort
if (len > 5) {
// Get a pivot element using the ternary method
let pivot = _mediant(arr, left, right)
/ * define two initial variables, in order to facilitate programming, we let the pointer to the start point to the starting position, I let j pointer to a location before end position, why it can be operation, because in our ternary function, we have hid the principal component in front of the last element, that is to say the last element must be than the main yuanta, You can skip */
let i = left
let j = right - 1
while (true) {
/ * because we in the front of the last element of an element is the main yuan, therefore, the main yuan also directly do not need to consider the location, so need to j - here, skip the current principal component location, to start cycle compared to the left, if j pointer found smaller than principal component elements (the worst came to the first), exit the loop * /
while (pivot < arr[--j]);
/* since our first element was swapped in the triplet function, this element must be smaller than the pivot element, so we need to do i++ first, skip the current element position, and then start the loop to the right, when we find the greater than the pivot element (worst case, find the pivot element position) to end the loop */
while (pivot > arr[++i]);
// If our two Pointers meet, the loop has moved all elements larger than the pivot to the back of the pivot, and all elements smaller than the pivot to the front of the pivot, and the loop is complete
if (i >= j) {
break
}
// Otherwise, the two elements where our two Pointers are now need to be swapped
_swap(arr, i, j)
}
// When the loop is complete, I and j have already met. At this point, the element at this position must be larger than the pivot element (because the exit condition of the inner loop is that the right pointer finds stops smaller than the pivot element, and the left pointer finds stops larger than the pivot element), so we can put the pivot element at this position.
arr[right - 1] = arr[i]
arr[i] = pivot
// Recursively divide the elements to the left of I
_quickSort(arr, left, i - 1)
// Recursively divide the elements to the right of I
_quickSort(arr, i + 1, right)
} else {
// Because left is the starting position of the current fragment to be sorted
_insertionSort(arr, left, len)
}
}
/** * defines the standard sort function interface, easy to call */
function quickSort(arr) {
return Array.isArray(arr) ? _quickSort(arr, 0, arr.length - 1) : arr
}
Copy the code4, summarize
The natural language description of quicksort is as follows:
0. If the current sequence fragment element to be sorted is less than or equal to 1, it does not need to move and ends directly; Otherwise, take an element as the pivot according to a certain strategy;
1. Move the left pointer to the right, find the value greater than the principal element, find the stop at the current position; Stop if the last element is not found;
2, the right pointer moves to the left, find less than the principal element, find stop at the current position; Stop if the first element is not found;
3. If the first and second steps are found, swap the small element with the large element (relative to the pivot);
4, when I pointer and j pointer meet, fill in the main element; Did not meet to continue to repeat one or two steps;
5. Recursively process the sequence to the left of the pointer I, recursively process the sequence to the right of the pointer I;
Quicksort is an improvement on bubble sort. The reason why quicksort is fast is that the element moves at a time with a particularly large stride; In addition, once the position of the middle element is determined during each element move, its position will not change.
Quicksort is an unstable sorting algorithm whose performance is determined by the bounding value we select. If the bounding value is poorly selected, the performance can be as low as O(N2, note: 2 is square) (bubble sort 🐶), and if the bounding value is well selected, the performance can be as high as O(N*logN).
Due to the limited level of the author, it is inevitable that there will be mistakes in the writing process. If there are any mistakes, please correct them. Please contact the author at [email protected], your opinions will help me make better progress. This article is the author’s original, if reproduced please contact the author.