YouTip2Way Quick Sort
# Two-Way Quick Sort
The two-way quick sort algorithm is an improved version of randomized quick sort. The partition process uses two index values (i, j) to traverse the array, placing elements **v** to the right of the position pointed to by index j, where **v** represents the pivot value.
### Applicable Scenarios
The time and space complexity are the same as randomized quick sort. For arrays with a large number of duplicate elements, using the randomized quick sort from the previous section is very inefficient. This can cause the subarrays after partition to be extremely unbalanced in length (either greater than or less than the pivot), potentially degrading to an O(n²) time complexity algorithm. In such cases, the two-way quick sort algorithm can be used.
### Process Illustration
Use two index values (i, j) to traverse the sequence. Place elements **=v** to the right of the position pointed to by index j, balancing the left and right subarrays.
!(#)
### Java Example Code
**Source Code Package Download:*## QuickSort2Ways.java File Code:
package ;
/**
* Two-Way Quick Sort
*/
public class QuickSort2Ways {
//Core code---start
private static int partition(Comparable[] arr, int l, int r){
// Randomly select a value as the pivot within the range arr[l...r]
swap( arr, l , (int)(Math.random()*(r-l+1))+l );
Comparable v = arr;
// arr[l+1...i) = v
int i = l+1, j = r;
while(true){
while( i <= r && arr.compareTo(v)= l+1&& arr.compareTo(v)>0)
j --;
if( i > j )
break;
swap( arr, i, j );
i ++;
j --;
}
swap(arr, l, j);
return j;
}
//Core code---end
// Recursively use quick sort to sort the range arr[l...r]
private static void sort(Comparable[] arr, int l, int r){
if(l >= r){
return;
}
int p = partition(arr, l, r);
sort(arr, l, p-1);
sort(arr, p+1, r);
}
public static void sort(Comparable[] arr){
int n = arr.length;
sort(arr, 0, n-1);
}
private static void swap(Object[] arr, int i, int j){
Object t = arr;
arr= arr;
arr= t;
}
// Test Quick Sort
public static void main(String[] args){
// Two-way quick sort is also an O(nlogn) complexity algorithm
// It can easily handle data at the million level within 1 second
// Quick Sort is also an O(nlogn) complexity algorithm
// It can easily handle data at the million level within 1 second
int N =1000000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
sort(arr);
SortTestHelper.printArray(arr);
}
}
* * *
## Detailed Algorithm Principle
The core of two-way quick sort lies in its **two-pointer partitioning method**. Unlike single-way quick sort (which scans from only one end), it uses two pointers that scan from the head and tail of the subarray towards the middle, ensuring that equal elements are not all pushed to one side.
### Core: Two-Way Partitioning Process
Assume we want to sort the part of array `arr` from index `left` to `right`.
**Select Pivot**: Randomly select an element from `arr[left...right]` as the pivot value `pivot`. Randomization is used to avoid the worst-case scenario on sorted arrays.
**Initialize Pointers**:
* `i = left + 1`: Pointer scanning from left to right, looking for the first element **greater than or equal to** `pivot`.
* `j = right`: Pointer scanning from right to left, looking for the first element **less than or equal to** `pivot`.
**Scanning and Swapping Loop**:
* `while` loop with condition `i = pivot`.
* Inner `while` loop: Move `j` continuously to the left until `arr <= pivot`.
* At this point, `arr` is a "large" element that shouldn't be in the left part, and `arr` is a "small" element that shouldn't be in the right part.
* If `i <= j` at this point, swap `arr` and `arr`, then `i++`, `j--`, and continue the outer loop.
**Place Pivot and Return Partition Point**:
* After the loop ends, `i` and `j` have crossed (`j < i`). Now `arr` (the pivot) needs to be placed in its correct position.
* Swap `arr` with `arr`. This is because the position where `j` finally stops points to the **last element less than or equal to the pivot**.
* Return `j` as the new partition point. Now, `arr[left...j-1] = pivot`, and `arr == pivot`.
### Recursive Sorting
After obtaining the partition point `p`, recursively apply the above process to the left subarray `arr[left...p-1]` and the right subarray `arr[p+1...right]` until the subarray length is 1.
* * *
## Code Implementation
Let's understand two-way quick sort concretely through a complete Java implementation.
### 1. Main Sorting Function
## Example
public class TwoWayQuickSort {
// Public sorting interface
public static void sort(int[] arr){
if(arr ==null|| arr.length= right boundary, subarray is already sorted or empty
if(left >= right){
return;
}
// Key step: perform two-way partition and return the index of the partition point
int p = partition(arr, left, right);
// Recursively sort the left half (left, p-1)
quickSort(arr, left, p -1);
// Recursively sort the right half (p+1, right)
quickSort(arr, p +1, right);
}
}
### 2. Core: Two-Way Partition Function
This is the core of the algorithm. Please understand it carefully in conjunction with the flowchart and comments above.
## Example
// Two-way partition function
private static int partition(int[] arr, int left, int right){
// 1. Randomly select a pivot and swap it to the left position to avoid worst-case on sorted arrays
int randomIndex = left +(int)(Math.random()*(right - left +1));
swap(arr, left, randomIndex);
int pivot = arr;// Pivot value
// 2. Initialize two pointers
// i: scan from left to right, looking for elements >= pivot
// j: scan from right to left, looking for elements <= pivot
int i = left +1;
int j = right;
// 3. Main loop: while i and j have not crossed
while(i = pivot
// Note boundary i <= right to prevent array out of bounds
while(i <= right && arr< pivot){
i++;
}
// 3.2 Move right pointer j: find the first element = left+1, because left position is the pivot itself
while(j >= left +1&& arr> pivot){
j--;
}
// 3.3 Check pointer status
// If i > j, scanning is complete, left and right partitions are ready, no swap needed
if(i > j){
break;
}
// 3.4 Swap arr and arr
// Now arr >= pivot, arr <= pivot, swapping them places large and small elements in their respective positions
swap(arr, i, j);
// After swapping, move pointers to continue scanning
i++;
j--;
}
// 4. Place the pivot in its final correct position j
// After the loop ends, j points to the last element <= pivot
swap(arr, left, j);
// 5. Return the partition point index j
return j;
}
// Helper function: swap the positions of two elements in the array
private static void swap(int[] arr, int i, int j){
int temp = arr;
arr= arr;
arr= temp;
}
}
### 3. Testing and Verification
Let's test our implementation with an array containing duplicate elements.
## Example
public class Main {
public static void main(String[] args){
// Test case 1: array with many duplicate elements
int[] arr1 ={4, 2, 2, 8, 3, 3, 1, 5, 3, 2};
System.out.println("Before sorting: "+Arrays.toString(arr1));
TwoWayQuickSort.sort(arr1);
System.out.println("After sorting: "+Arrays.toString(arr1));
// Test case 2: randomly generated large array
int[] arr2 =new int;
Random rand =new Random();
for(int i =0; i < arr2.length; i++){
arr2= rand.nextInt(50);// Generate random numbers 0-49, likely to have duplicates
}
System.out.println("n Random array before sorting: "+Arrays.toString(arr2));
TwoWayQuickSort.sort(arr2);
System.out.println("Random array after sorting: "+Arrays.toString(arr2));
// Verify if the sorting result is correct
for(int i =1; i < arr2.length; i++){
if(arr2< arr2){
System.out.println("Sorting error!");
return;
}
}
System.out.println("Sorting result verification passed!");
}
}
**Test Data Output Example**:
Before sorting: [4, 2, 2, 8, 3, 3, 1, 5, 3, 2]After sorting: [1, 2, 2, 2, 3, 3, 3, 4, 5, 8]Random array before sorting: [17, 33, 12, 48, 8, 2, 41, ...]Random array after sorting: [2, 8, 12, 17, 33, 33, 41, 48, ...]Sorting result verification passed!
* * *
## Algorithm Analysis and Comparison
### Time Complexity
* **Average Case**: $O(n log n)$. Two-way quick sort balances the distribution of duplicate elements, making the recursion tree relatively balanced.
* **Worst Case**: $O(n^2)$. Although random pivot selection greatly reduces the probability, the worst case still occurs if every partition is extremely unbalanced (e.g., the pivot is always the current minimum or maximum value).
* **Best Case**: $O(n log n)$. Every partition divides the array evenly.
### Space Complexity
* Primarily the space occupied by the recursive call stack.
* Average depth is $O(log n)$, worst-case depth is $O(n)$.