Quick sort

What is quicksort? Quicksort was proposed by the Turing Award winner CAR Hoare (1934--) in 1960.

Quick sort is an improvement to bubble sort. Its basic idea is: divide the data to be sorted into two independent parts by sorting, and all the data in one part is smaller than all the data in the other part, and then separate the two parts of data according to this method For quick sorting, the entire sorting process can be performed recursively, so that the entire data becomes an ordered sequence. The entire sorting process only requires three steps:

• In the data set, select an element as the "pivot".
• All elements smaller than "reference" are moved to the left of "reference"; all elements greater than "reference" are moved to the right of "reference".
• Repeat the first and second steps for the two subsets on the left and right of the "benchmark" until there is only one element left in all the subsets.

Quoting from wikipedia Quicksort (English: Quicksort), also known as partition-exchange sort (partition-exchange sort), a sorting algorithm, first proposed by Tony Hall. On average, it takes Ο (n log n) comparisons to sort n items. In the worst case, Ο(n2) comparisons are required, but this situation is not common. In fact, quicksort is usually significantly faster than other Ο(n log n) algorithms, because its inner loop can be implemented efficiently on most architectures.

step

1. Find the base point (middle number) of the array, and create two empty arrays left and right;
2. Traverse the array, take out each number in the array and compare with the reference point, if it is smaller than the reference point, put it in the left array, if it is larger than the reference point, put it in the right array;
3. Recursively call the arrays left and right.

method one

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

      for (var i =0; i <arr.length; i++) {
        if (arr[i] < base) {
          left.push(arr[i])
        }else {
          right.push(arr[i])
        }
      }

      return quickSort(left).concat([base], quickSort(right));
    }

Implement a quickSort encapsulation, and define left and right, find the base Dot of the array and the corresponding base base, then traverse each item of the array to compare with base, and finally call it recursively to give an exit conditionif (arr.length <= 1) {return arr;}

Method Two

function quickSort(array, left, right) {
      var length =array.length;
        left =typeof left ==='number'? left :0,
        right =typeof right ==='number'? right : length-1;

        if (left < right) {
            var index = left -1;
            for (var i = left; i <= right; i++) {
                if (array[i] <= array[right]) {
                    index++;
                    var temp = array[index];
                    array[index] = array[i];
                    array[i] = temp;
                }
            }
            quickSort(array, left, index -1);
            quickSort(array, index +1, right);
        }
        return array;
    }

The basic idea of ​​quick sort is divide and conquer

Quoted from wikipedia In computer science, divide and conquer is an important algorithm paradigm based on multiple branch recursion. The literal interpretation is "divide and conquer", that is, to divide a complex problem into two or more identical or similar sub-problems until the final sub-problem can be solved simply and directly. The solution of the original problem is the combination of the solutions of the sub-problems. .

Improved method of quick sort: three-way quick sort

definition

Three-way quick sort is an optimized version of quick sort. It divides the array into three segments, which are less than the reference element, equal to the reference element, and greater than the reference element. In this way, the situation where the same elements exist in the array can be processed more efficiently. Other features are more rapid The ordering is basically the same.

Let me briefly summarize the ideas here. Interested students can read on the link above: [Quick Sorting and Optimization (Java Implementation)] [Java]

• Randomly select the base value base (randomly selected pivot), refer to [Summary of Optimization Ideas for Quick Sort Algorithm] 
• With the use of insertion sort (when the problem size is small, almost ordered, insertion sort performance is very good)
• When there is a large amount of data and there are many repetitions, use three-way quick sorting

    
      
       console.time("test0")
       function qSort(arr) {
        if(arr.length == 0) {
         return [];
        }
        var left = [];
        var right = [];
        var pivot = arr[0];
        for(var i = 1; i < arr.length; i++) 
         if(arr[i] < pivot) {
          left.push(arr[i]);
         } else {
          right.push(arr[i]);
         }
        }
        return [...qSort(left), pivot, ...qSort(right)];
       }
       console.log(qSort([9, 4, 10, 3, 1, 1, 0, 10, 8, 3, 9, 9, 4, 10, 10, 9, 9, 9, 1, 0]));
       console.timeEnd("test0")
      
       console.time("test1")
       function qSort3(arr) {       
        if(arr.length == 0) {
         return [];
        }
        var left = [];
        var center = [];
        var right = [];
        var pivot = arr[0];    
        for(var i = 0; i < arr.length; i++) {      
         if(arr[i] < pivot) {
          left.push(arr[i]);
         } else if(arr[i] == pivot) {
          center.push(arr[i]);
         } else {
          right.push(arr[i]);
         }
        }
        return [...qSort3(left), ...center, ...qSort3(right)];
       }
       console.log(qSort3([9, 4, 10, 3, 1, 1, 0, 10, 8, 3, 9, 9, 4, 10, 10, 9, 9, 9, 1, 0]))
       console.timeEnd("test1")
      

It can be seen that the optimization of data with duplicate data is still considerable.