Home > Web Front-end > JS Tutorial > body text

Detailed explanation of the algorithm for implementing Quicksort in Javascript_javascript skills

WBOY
Release: 2016-05-16 15:40:43
Original
1024 people have browsed it

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) {
};
Copy after login

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; }
};
Copy after login

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 = [];
};
Copy after login

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]);
    }
  }
};
Copy after login

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(","));
Copy after login

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

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template