YouTip3Way Qiuck Sort
## Three-Way Partitioning Algorithm
**Three-Way Partitioning Algorithm** is a special variant of quick sort, specifically optimized for handling arrays containing a large number of duplicate elements. Its core idea is to divide the array into three parts during one partition process, rather than the traditional two parts.
Three-Way Quick Sort is a further improved version of Two-Way Quick Sort. The three-way sorting algorithm divides the data to be sorted into three parts: less than v, equal to v, and greater than v, where v is the pivot value. In these three parts, the data equal to v does not need to be sorted in the next recursion, and the data less than v and greater than v will not have one particularly large case). Through this method, the Three-Way Quick Sort algorithm has better performance.
Imagine you have a large bucket of mixed colored marbles, with red, white, and blue three colors. Your task is to quickly separate them so that all red marbles are on the left, white in the middle, and blue on the right. The Three-Way Partitioning Algorithm is the sorting master for solving such problems.
### Traditional Quick Sort vs Three-Way Quick Sort
Let's use a simple table to compare the differences between the two:
| Feature | Traditional Quick Sort | Three-Way Quick Sort |
| --- | --- | --- |
| **Number of Partitions** | 2 (less than pivot, greater than pivot) | 3 (less than pivot, equal to pivot, greater than pivot) |
| **Handling Duplicate Elements** | Less efficient, duplicate elements may be compared and swapped multiple times | Very efficient, duplicate elements are processed together |
| **Time Complexity** | Average O(n log n), Worst O(n²) | Average O(n log n), Worst O(n²) |
| **Space Complexity** | O(log n) (recursion stack) | O(log n) (recursion stack) |
| **Applicable Scenarios** | General sorting, low element duplication rate | High element duplication rate, such as color sorting, score segmentation |
### Applicable Description
Time and space complexity are the same as randomized quick sort.
The Three-Way Quick Sort algorithm uses a three-way partitioning strategy to partition the array, which is very effective for processing arrays with a large number of duplicate elements, improving the quick sort process. It adds logic to handle values equal to the partition element, concentrating all values equal to the partition element together.
### Process Illustration
!(#)
We discuss three cases for the partition process, where i represents the current index position being traversed:
(1) If the currently processed element e=V, element e is directly included in the blue region, and i moves back one position.
!(#)
(2) If the currently processed element ev, e is swapped with the value at the gt-1 index position, and the gt index moves forward one position.
!(#)
Finally, when i=gt, the traversal ends, and it is necessary to swap v with the value pointed to by index lt. Thus, the sorting process is complete. Then, the same method is used to recursively sort the array parts V.
### Java Example Code
**Source Package Download:*## QuickSort3Ways.java File Code:
package tutorial;
/**
* 3-Way Quick Sort
*/
public class QuickSort3Ways {
//Core code---Start
// Recursively apply quick sort,onarr[l...r]'sSort the range
private static void sort(Comparable[] arr, int l, int r){
if(l >= r){
return;
}
// Randomly in arr[l...r]in the range of, Select a value as the pivot point
swap( arr, l, (int)(Math.random()*(r-l+1))+ l );
Comparable v = arr;
int lt = l;// arr[l+1...lt] v
int i = l+1;// arr[lt+1...i) == v
while( i < gt ){
if( arr.compareTo(v)0){
swap( arr, i, gt-1);
gt --;
}
else{// arr == v
i ++;
}
}
swap( arr, l, lt );
sort(arr, l, lt-1);
sort(arr, gt, r);
}
//Core code---End
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 QuickSort3Ways
public static void main(String[] args){
// 3-Way Quick SortThe algorithm also has O(nlogn) complexity'sAlgorithm
// Can easily handle 1 million scale within 1 second'sData
int N =1000000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
sort(arr);
SortTestHelper.printArray(arr);
}
}
* * *
## Algorithm Core Idea and Working Principle
The subtlety of the Three-Way Partitioning Algorithm lies in using three pointers to track different regions of the array, completing three classifications in one traversal.
### Algorithm Partition State
Let's understand the algorithm's partitioning process through a state diagram:
!(#)
**Figure Description**: The algorithm maintains three pointers (`lt`, `i`, `gt`) that divide the array into four regions. As processing progresses, the unprocessed region gradually shrinks, eventually forming three clear partitions.
### The Role of Three Key Pointers
1. **`lt` (less than) pointer**: Points to the end of the region less than the pivot value
2. **`i` (current) pointer**: The position of the element currently being checked
3. **`gt` (greater than) pointer**: Points to the beginning of the region greater than the pivot value
* * *
## Python Implementation
### Basic Three-Way Partition Function
Below is the implementation of a standard three-way partition function, which we will analyze line by line:
## Example
def three_way_partition(arr, low, high):
"""
onArray arr 's low to high Perform 3-way partition on the range
Parameter:
arr: To be partitioned'sArray
low: Partition start index
high: Partition end index
Return:
(lt, gt): Equal-to-pivot region'sLeft and right boundaries
"""
# Choose pivot (here we choose the first element)
pivot = arr
# Initialize three pointers
lt = low # Less-than-pivot region'sRight boundary (initially low)
i = low + 1# Currently checking'sElement position
gt = high # Greater-than-pivot region'sLeft boundary (initially high)
# Main loop: while there are unprocessed'selements, continue
while i <= gt:
if arr< pivot:
# Case 1: Current element is less than pivot
# It with the lt pointer'sSwap with the next element, expand the less-than region
arr, arr= arr, arr
lt +=1
i +=