Dual-Pivot Quick Sort

I. Concept and Introduction

The dual-pivot 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 left of the position pointed to by index i, and elements >v to the right of the position pointed to by index j, where v represents the pivot value.

II. Applicability

The time and space complexity are the same as randomized quick sort. For arrays with a large number of duplicate elements, using the previous randomized quick sort can be very inefficient, leading to highly unbalanced sub-arrays after partition, and even degenerating into an algorithm with O(n^2) time complexity. For such cases, the dual-pivot quick sort algorithm can be used.

III. Process Diagram

Using two index values (i, j) to traverse the sequence, elements <=v are placed to the left of the position pointed to by index i, and elements >=v are placed to the right of the position pointed to by index j, balancing the sub-arrays on both sides.

IV. Java Example Code

Source Code Download: Download

QuickSort2Ways.java File Code:

package tutorialpro;

/**
 * Dual-Pivot Quick Sort
 */
public class QuickSort2Ways {

    // Core code---start
    private static int partition(Comparable[] arr, int l, int r) {
        // Randomly select a pivot within the range of arr[l...r]
        swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);
        Comparable v = arr[l];
        // arr[l+1...i) <= v; arr(j...r] >= v
        int i = l + 1, j = r;
        while (true) {
            while (i <= r && arr[i].compareTo(v) < 0)
                i++;
            while (j >= l + 1 && arr[j].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[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // Test QuickSort
    public static void main(String[] args) {
        // Dual-Pivot Quick Sort is also an O(nlogn) complexity algorithm
        // It can easily handle 1 million pieces of data within 1 second
        int N = 1000000;
        // Quick Sort is also an O(nlogn) complexity algorithm
        // It can easily handle 1 million pieces of data within 1 second
    }
}

Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
sort(arr);
SortTestHelper.printArray(arr);