Three-Way QuickSort Algorithm

I. Concept and Introduction

Three-Way QuickSort is an improved version of the dual-pivot QuickSort. This algorithm divides the data into three parts: less than v, equal to v, and greater than v, where v is the pivot value. In this way, the data equal to v does not need to be sorted in the next recursion, and neither the data less than v nor greater than v will have an excessive number of elements in one part. This method enhances the performance of the Three-Way QuickSort algorithm.

II. Applicability

The time and space complexity are the same as randomized QuickSort.

The Three-Way QuickSort algorithm uses a three-way partitioning strategy to divide the array, which is highly effective for arrays with many duplicate elements. It adds logic to handle elements equal to the pivot value, grouping all such elements together.

III. Process Diagram

We discuss the partition process in three cases, where i represents the current index being traversed:

1. The current element e = V is directly included in the blue interval, and i is incremented by one.
2. The current element e < v is swapped with the first element in the equal-V interval, and both indices lt and i are incremented by one.
3. The current element e > v is swapped with the element at index gt-1, and the gt index is decremented by one.

When i = gt, the traversal ends, and the pivot v is swapped with the element at index lt. This completes the sorting process. Then, the parts of the array less than V and greater than V are sorted recursively using the same method.

IV. Java Example Code

Source Code Download: Download

QuickSort3Ways.java File Code:

package tutorialpro;

/**
 * Three-Way QuickSort
 */
public class QuickSort3Ways {
    // Core code---start
    // Recursively use QuickSort to sort the range arr[l...r]
    private static void sort(Comparable[] arr, int l, int r){
        if (l >= r) {
            return;
        }
        // Randomly select a value within the range arr[l...r] as the pivot point
        swap(arr, l, (int)(Math.random()*(r-l+1)) + l);
        Comparable v = arr[l];
        int lt = l;     // arr[l+1...lt] < v
        int gt = r + 1; // arr[gt...r] > v
        int i = l + 1;  // arr[lt+1...i) == v
        while(i < gt){
            if(arr[i].compareTo(v) < 0){
                swap(arr, i, lt+1);
                i++;
                lt++;
            }
            else if(arr[i].compareTo(v) > 0){
                swap(arr, i, gt-1);
                gt--;
            }
            else{ // arr[i] == 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[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // Test QuickSort3Ways
    public static void main(String[] args) {
        // The Three-Way QuickSort algorithm is also an O(nlogn) complexity algorithm
    }
}

This is an Chinese to English translation, please provide the English translation for this text. Do not provide any explanations or text apart from the translation. Chinese: // Can easily handle data in the millions within 1 second int N = 1000000; Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000); sort(arr); SortTestHelper.printArray(arr); } }

English: // Can easily handle data in the millions within 1 second
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        SortTestHelper.printArray(arr);
    }
}