This is the 19th day of my participation in the August More Text Challenge

Quick sort

  • Quicksort: Divide the original array into smaller arrays using divide-and-conquer.
  • Core ideas:
    • First, select from the arrayIn the middle of aIt’s the pivot element.
    • Next, (partition operation) :Create two Pointers, the left one points to the first item of the array, and the right one points to the last item of the array.
    • And then, movePointer to the leftUntil one is foundThan the main yuantaThe element; Then movePointer to the right, find oneSmaller than the primaryThe element. They are then swapped and the process is repeated until the left pointer exceeds the right.
    • And what we’re doing is we’re putting everything that’s smaller than the pivot entry before the pivot entry, and everything that’s bigger than the pivot entry after the pivot entry. (End of division operation)
    • The algorithm then repeats the process for the partitioned small array (subarrays of elements smaller than the pivot, and subarrays of elements larger than the pivot) until the array is completely sorted.

implementation

// We declare a main method to call the recursive function, passing the array to be sorted, and index 0 and its last position
function quickSort(array) {
    quick(array, 0, array.length -1)}// Implement the quick recursive function
function quick(array, left, right) {
    // Define index to mark the primary location
    let index = null;
    // Sort only when the array is greater than 1
    if (array.length > 1) {
        // Index = 0 and length-1
        index = partition(array, left, right);
        // 
        if (left < index -1) {
            quick(array, left, index-1)}if (index < right) {
            quick(array, index,right)
        }
    }
}


// Partition function
function partition(array, left, right) {
    / / in the first place. Determines the middle subscript element of the array as the primary element
    let pivot = array[Math.floor((left + right) / 2)];
    // Initialize two Pointers, left 0 and right length-1, passed in
    let i = left;
    let j = right;
    // Start the loop as long as the two Pointers are not interleaved, otherwise return I
    while(i <= j) {
        // Move the left pointer until an element larger than the pivot element is found
        while(array[i] < pivot) {
            i++
        }
        // Then move the right pointer until you find an element smaller than the pivot
        while(array[j] > pivot) {
            j--
        }
        // When the left pointer is larger than the main element and the right pointer is smaller than the main element, the left pointer index is less than or equal to the right pointer. That is, when the left term is larger than the right term
        if(i <= j) {
            // Switch the positions of the two terms
            let aux = array[i];
            array[i] = array[j]
            array[j] = aux;
            // Move the pointer so that the next operation repeats the process
            i++
            j--
        }
    }
    // When the partition is complete, return the index of the left pointer, which is used to create the subarray
    return i
}

Copy the code