Introduction to the


Like bubble sort, quicksort is a swap sort, where elements are compared and swapped.

The difference is that bubble sort bubbles only one element to one end of the array in each round, whereas quicksort splits the array into two parts by picking a base element in each round and moving other elements larger than it to one side and smaller elements to the other.

  • Purple: base element
  • Green: Element larger than the base element
  • Yellow: An element smaller than the base element

This idea is called didivide and conquer. Given an array like the one above, bubble sort typically requires seven rounds of comparison, each of which moves one element to one end of the array, in time O(n^).


Selection of the base element


Pivot element, in divide-and-conquer, moves other elements to its sides from the center of the pivot element’s bit

  1. In general, the easiest way is to select the first element of the sequence
  2. Select a random element as the base element and swap the base element with the first element of the sequence


Quicksort process:


First, select the base element Pivot, and set the left and right Pointers to the left and right elements

       

  • First cycle

The right pointer starts by comparing the element to the base element. The pointer moves to the left if it is greater than or equal to the base element, and stops moving right if it is less than the base element. If the current sequence 7 > 5 moves to the left and 1 < 5 stops moving, switch the left pointer.

The left pointer starts, comparing the element to the base element. If less than or equal to the base element, the pointer moves to the right, if greater than the base element, the left pointer stops moving, 8 > 5 stops moving

When both right and left are stopped, let the elements pointed to by the left and right Pointers switch positions

  • Second cycle

Switch to the right pointer, move right to the left, move right to 2, stop when 2 < 5

Switch to left pointer, move left to 6, 6 > 5 stop moving

  • Third cycle

I’m gonna go to right, I’m gonna go to the left and I’m gonna go to 9, 9 > 5 and I’m gonna go to the left and I’m gonna go to 3, 3 < 5 and I’m gonna stop

Switch to the left pointer, move right left to 3, overlap with right, and swap base element 5 with overlap element 3

This is where the first round of “probing” really ends. In this case, base number 5 is the cut-off point, and everything to the left of 5 is greater than or equal to 5 and everything to the right of 5 is greater than or equal to 5.


Now the base element 5 has been repositioned, at this time, we split it into two sequences with 5 as the cut-off point, the sequence on the left [3,1,2] and the sequence on the right [9,6,8,7], and then we need to process these two sequences respectively


Left sequence:

  • First cycle

Starting with the right pointer, 2 < 3 stops moving

Switch to the left pointer, 1 < 3 continues to move to the right, left and right overlap, and swap elements

Base element 3 is in place, and we need to process the sequence to the left of base element 3 [2,1].


Sequence on the right:


Starting with the right pointer, 7 < 9 stops moving

Switch to the left pointer, 6 < 9 continues to move to the right, and 8 < 9 continues to move to the right to overlap with the right pointer, swapping elements

Now that base element 9 is in place, we need to process the sequence left of base element 9 [7,6,8]

The resulting sequence is as follows: [1,2,3,5,6,7,8]

Under the divide-and-conquer idea, the original sequence is divided into two parts in each round, and each part is divided into two parts in the next round, until it can no longer be divided.

Algorithm processing process:

Code:

/** * quicksort */
public class demo3 {

    public static void main(String[] args) {
        int array[] = {5.8.6.3.9.2.1.7};
        quickSort(array,0,array.length-1);
        System.out.printf(Arrays.toString(array));
    }


    public static void quickSort(int[] arr,int startIndex,int endIndex){
        // End of recursion
        if(startIndex >= endIndex){
            return;
        }
       // Take the first position as the base element
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while(left ! = right){// Control the comparison of the right pointer and move it left
            while (left < right && arr[right] > pivot){
                right--;
            }
            // Control the left pointer comparison and move it right
            while (left < right && arr[left] <= pivot){
                left++;
            }
            if(left<right){
                intp = arr[left]; arr[left] = arr[right]; arr[right] = p; }}// Pivot and pointer overlap point switch
        arr[startIndex] = arr[left];
        arr[left] = pivot;

        quickSort(arr,startIndex,right - 1);
        quickSort(arr,right + 1,endIndex); }}Copy the code

[1, 2, 3, 5, 6, 7, 8, 9]

“When there is a high wind, life does not give up”