preface
In the last article “sorting algorithm: Understanding and implementation of quicksort”, I will implement it in accordance with the ideas described in the book, we read my article to remind me that the implementation of my sorting algorithm is not optimal, non-in-situ quicksort, will cause additional memory waste, and the performance is not very good.
This article with you to explain the optimal implementation of quick sort: three way fast row, and the use of JavaScript to achieve it, three way fast row is a fast row in situ, but also very good performance, welcome interested front-end developers to read this article
concept
Find a reference value (PIOVT) randomly from the sequence, move the elements in the sequence to partition, move the elements smaller than the reference value to the left partition, move the elements equal to the reference value to the middle partition, and move the elements larger than the reference value to the right partition. After the partition is complete, fast-sort the elements in the left and right partitions respectively.
The illustration example
As shown in the figure, we set element 0 in the array to the reference value (PIOVT), set it to P, and divide the elements into three parts: less than P, equal to P, and greater than P.
Element I refers to the element currently being compared, L is the start of the array, and R is the end of the array.
The interval [L+1,lt] is the element less than P, and the interval [lt+1,i-1] is the element equal to P. The interval [gt,R] is formed from R on the right to store the element greater than P.
At the beginning of sorting, these intervals do not exist, so we need to determine the boundary. The initial index of I points to L+1, the initial value of lt is L, and the initial value of gt is R+1, indicating that these three intervals are empty.
With JS to achieve three way fast row
After sorting out the above diagrams, the realization ideas are as follows:
- If the current element I refers to is equal to p, then I +1
- If the current element I points to is less than p, then the element at lt+1 is swapped with the value at index I, then lt+1, and I +1
- If the current element I points to is greater than p, the element at GT-1 is swapped with the value at index I, and then GT-1
- Finally, when I goes to gt, gt== I; Lt-1; lt-1; lt-1; lt-1; So we have the three intervals that we want, less than p, equal to p, greater than p
Next, let’s translate the above implementation ideas into code
- Implement partition function, used to return: < p, and greater than p element interval information
/** ** @param arr Array to be quicksorted * @param L the start position of the array * @param R the end position of the array * @returns {{lt: *, gt: *}} */
const partition = function (arr, L, R) {
// The reference value is the zero element of the array
let p = arr[L];
// The initial value of the left interval is L
let lt = L;
// The initial value of the right interval is R+1
let gt = R + 1;
for (let i = L + 1; i < gt;) {if(arr[i] === p){
// The element to which I refers is equal to p
i++;
} else if(arr[i] > p){
// Swap the element at GT-1 with the element at the current index, gt--
[arr[gt - 1],arr[i]] = [arr[i],arr[gt - 1]];
gt--;
}else{
// The current element I points to is less than p. Swap the element at lt+1 with the element at the current index, lt+1, I +1
[arr[lt + 1],arr[i]] = [arr[i],arr[lt + 1]]. lt++; i++; }}// When I goes to GT, the rest of the space has been partitioned except for the elements at the base value. Swap the base value with the elements at lt, lT-1, and finally get the three intervals we need
[arr[L],arr[lt]] = [arr[lt],arr[L]];
lt--;
console.log('Array after three fast rows:${arr}`);
return {lt : lt, gt : gt};
}
Copy the codeTest the partitioning function
const dataArr = [3.5.8.1.2.9.4.7.6];
console.log(partition(dataArr,0,dataArr.length - 1));
Copy the code
- Realize three way fast sorting function
const threeWayFastRow = function (arr,L,R) {
Exit recursion when the start position of the current array is greater than or equal to the end of the array
if(L >= R){
return false;
}
let obj = partition(arr, L, R);
// Recursive execution: triple quicksort elements with no interval greater than or less than p
threeWayFastRow(arr,L,obj.lt);
threeWayFastRow(arr,obj.gt,R);
}
Copy the codeThree – way fast platoon test
console.time("Three-way express platoon");
const dataArr = [3.5.8.1.2.9.4.7.6];
threeWayFastRow(dataArr,0,dataArr.length - 1);
console.log('Three quick row completed:${dataArr}`);
console.timeEnd("Three-way express platoon");
Copy the code
Compare ordinary fast row and three way fast row
Let’s compare the running speed of the ordinary quicksort written in the last article with the three-way quicksort written in this article. Let’s see which sort is faster.
- We randomly generated an array of 10,000 out-of-order elements and tested it with quicksort and three-way quicksort
// Other parts are omitted
/** * Generate a random array * @param count * @returns {[]} */
const randomArray = function(count){
let arr = [];
for (let i = 0; i < count; i++) {
arr[i] = Math.floor(Math.random() * 50 + 1);
}
return arr;
}
// **** other parts are omitted ****
// Generate an array
const dataArr = randomArray(10000);
console.time("Ordinary quick platoon");
quickSort(dataArr);
console.timeEnd("Ordinary quick platoon");
// **** three quick row other parts omitted ****
// Generate an array
const dataArr = randomArray(10000);
console.time("Three-way express platoon");
threeWayFastRow(dataArr,0,dataArr.length - 1);
console.timeEnd("Three-way express platoon");
Copy the code- Result of ordinary fast queue execution
- Result of three-way fast queue execution
The result shows that the sorting efficiency of three-way quicksort is twice as high as that of ordinary quicksort.
Write in the last
- If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
- This article was first published in nuggets. Reprint is prohibited without permission 💌