Detailed explanation of the algorithm for implementing Quicksort in Javascript_javascript skills

Currently, there are about seven or eight most common sorting algorithms, among which "Quicksort" is the most widely used and faster. It was proposed by Turing Award winner C. A. R. Hoare (1934--) in 1960.

The idea of ​​"quick sort" is very simple. The whole sorting process only requires three steps:

(1) In the data set, select an element as the "pivot".

(2) All elements smaller than "base" are moved to the left of "base"; all elements larger than "base" are moved to the right of "base".

(3) Repeat the first and second steps for the two subsets on the left and right of the "baseline" until only one element remains in all subsets.

For example, there is a data set {85, 24, 63, 45, 17, 31, 96, 50}. How to sort it?

The first step is to select the middle element 45 as the "baseline". (The base value can be chosen arbitrarily, but choosing a value in the middle is easier to understand.)

The second step is to compare each element with the "baseline" in order to form two subsets, one "less than 45" and the other "greater than or equal to 45".

The third step is to repeat the first and second steps for the two subsets until only one element remains in all subsets.

The following refers to the information on the Internet and uses Javascript language to implement the above algorithm.

First, define a quickSort function whose parameter is an array.

var quickSort = function(arr) {
};

Then, check the number of elements in the array, and if it is less than or equal to 1, return it.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
};

Next, select the "pivot" and separate it from the original array, and then define two empty arrays to store two subsets, one left and one right.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2) ;
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
};

Then, start traversing the array, putting elements smaller than the "baseline" into the left subset, and elements larger than the "baseline" into the right subset.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2) ;
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
};

Finally, use recursion to repeat this process to get the sorted array.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1);
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat(pivot, quickSort(right));
};
 
var dataArray = [85,24,63,45,17,31,96,50];
console.log(dataArray.join(","));
console.log(quickSort(dataArray).join(","));

I hope this article will be helpful to everyone’s JavaScript programming design.