Example code for implementing randomized quick sorting in JS

Example code for implementing randomized quick sorting in JS_javascript skills

WBOY

Release： 2016-05-16 17:27:19

Original

1082 people have browsed it

The average time complexity of the algorithm is O(nlogn). But when the input is a sorted array or an almost sorted input, the time complexity is O(n^2). In order to solve this problem and ensure that the average time complexity is O(nlogn), the method is to introduce a preprocessing step, whose only purpose is to change the order of elements to random order. This preprocessing step can run in O(n) time. Another simple method that can achieve the same effect is to introduce a random element into the algorithm. This can be achieved by randomly choosing the pivot of the split element. The result of randomly selecting pivots relaxes the step to the point where all permutations of the input elements are equally likely. This step is introduced to modify the original quick sort, and the randomized quick sort shown below can be obtained. The new algorithm just randomly selects an index v in the interval [low...high], exchanges A[v] and A[low], and then continues according to the original quick sort algorithm. Here, parseInt(Math.random()*(high-low 1) low) returns a number between low and high.

Copy code The code is as follows:

　
/*****************************************
 Algorithm: split
 Input: Array A[low...high]
 Output: 
 1. If necessary, output the array A rearranged as described above; 
 2. Divide the new position w of element A[low]; 
*****************************************/
function split(array, low, high) {
　var i = low;
　var x = array[low];
　for(var j = low 1; j <= high; j ) {
 if(array[j] <= x) {
i ;
if(i != j) {
var temp = array[i];
array[i] = array[ j];
array[j] = temp;
}
}
}
temp = array[low];
array[low] = array[i];
array[i] = temp;
 return i;
}
 /*****************************************
 Algorithm: rquicksort
 Input: A [0...n-1]
 Output: Array array A[0...n-1]
 in non-descending order rquicksort(A, 0, n-1);
 **** ************************************/
 function rquicksort(array, low, high) {
 if(low < high) {
　/******Randomize the pivot of split elements*****/
　var v = parseInt(Math.random()*(high-low 1) low);
　var tmp = array[low];
array[low] = array[v];
 array[v] = tmp;
 /******Randomize the pivot of split elements*****/
 var w = split(array, low, high);
 rquicksort(array, low, w -1);
 rquicksort(array, w 1, high); 
 return array; 
 }
 }
 var array = [33, 22, 11 , 88, 23, 32];
array = rquicksort(array, 0, array.length-1);
console.log(array);