Java for Quick Sort and Three-way Quick Sort

Quick Sort Ideas

Select an element in the array (usually the first element of the array) as a reference object, arrange elements in the array smaller than the reference object to the left of the array, and elements larger than the reference object to the right of the array.

Quick sorting steps

  1. With the first element a[0] of the array a[N] as the reference object, two pointers i and j are set to point to the positions of the array subscripts 1 and N-1, respectively.
  2. Move pointer I until a[i] > a[0] is satisfied
  3. Move pointer J until a[j] < a[0] is satisfied
  4. Exchange a[i] and a[j]
  5. Continue to find and exchange the next a[i] and a[j] that meet the criteria until I >= J
  6. Swap a[0] with a[j]
  7. Recursively invoke the above steps on two subarrays, using a[j] (a[0], before swapping) as the delimitation point

code implementation

public void quickSort(int[] array, int low, int high) {
    if (low >= high) {
        return;
    }
    int mid = divide(array, low, high);//Find the correct position of the first element of the array in the array
    quickSort(array, low, mid-1);//Recursively invoke the sort method on two subarrays
    quickSort(array, mid+1, high);
}
public int divide(int[] array, int low, int high) {
    int a = array[low];//Select first element as reference
    int i = low + 1;//Left Pointer
    int j = high;//Right Pointer
    while(i <= j) {
        while(array[i] <= a) {//Find the element position on the left side of the array larger than the reference
            if (i >= j) {return;}//Prevent pointer movement from crossing bounds
            i++;
        }
        while(array[j] > a) {//Find an element position smaller than the reference to the right of the array
            if (j <= i) {return;}
            j--
        };
        swap(array, i++, j--);//Swap large elements on the left with small elements on the right
    }
    swap(array, low, j);
    return j;//The position where the pointer stops is the correct position of the first element in the array
}

3-way Quick Sort

background

If there are a large number of duplicate elements in the array, the normal quick sort will re-slice all the duplicate elements and sort them recursively.In fact, once the position of one element is determined, the position of the other repeating elements should also be determined (the repeating elements hug together).Quick three-way sorting optimizes this problem.

public void multiQuickSort(int[] array, int low, int high) {
    if(low >= high){
        return;
    }
    int i = array[low];//Point to the reference element, or rather, always to the first of all the repeating reference element
    int j = i + 1;//Point to the lower element to be sorted
    int k = high;//Point to high-order elements to be sorted
    while(j <= k) {
        if (a[j] < a[i]) {
            swap(array, i, j);//Arrange reference elements to the front, smaller than the back
            i++;//Self-increasing is to keep the pointer pointing to the reference element
            j++;//Point to the next lower element to be sorted
        } else if (a[j] == a[i]) {
            j++;//Skip duplicate reference element
        } else {
            swap(array, j, k);//Swap low and high elements to be sorted
            k--;//Decremental, pointing to the next higher element to be sorted
        }
    }//After jumping out of the loop, elements that are the same as the reference elements gather together 
    multiQuickSort(array, low, i - 1);//Duplicate elements can be separated from subarrays to be sorted on recursion
    multiQuickSort(array, j, high);
}

Posted on Thu, 14 May 2020 09:31:15 -0700 by advancedfuture