Randomized Quick Sort

I. Concept and Introduction

Quick Sort was proposed by C. A. R. Hoare in 1960.

Basic idea of Randomized Quick Sort: By a single pass, the data to be sorted is partitioned into two independent parts, where all data in one part are smaller than all data in the other part. Then, Quick Sort is applied to these two parts respectively. The entire sorting process can be performed recursively to achieve a sorted sequence.

II. Applicability

Quick Sort is a relatively fast sorting algorithm, with an average running time of O(nlogn). Its speed is due to the very concise and highly optimized inner loop, although the worst-case performance is O(n^2). Like Merge Sort, Quick Sort is a divide-and-conquer recursive algorithm. In terms of space performance, Quick Sort only requires auxiliary space for one element, but it also needs stack space for recursion, resulting in a space complexity of O(logn).

III. Process Illustration

In an array, select a pivot, such as the first position's 4, and move 4 to the correct position so that the subarray before 4 contains data smaller than 4, and the subarray after 4 contains data larger than 4. Then recursively proceed with the entire sorting.

How to move the selected pivot data to the correct position is the core of Quick Sort, known as Partition.

The process is as follows, where i is the current position of the element being compared:

This partition process is represented in code as:

private static int partition(Comparable[] arr, int l, int r) {
    Comparable v = arr[l];
    int j = l;
    for (int i = l + 1; i <= r; i++)
        if (arr[i].compareTo(v) < 0) {
            j++;
            // Swap array elements
            swap(arr, j, i);
        }
    swap(arr, l, j);
    return j;
}

If Quick Sort is applied to nearly sorted arrays, the subarrays after partition can be highly unbalanced, easily degenerating into an O(n^2) time complexity algorithm. We need to optimize the above code by randomly selecting a pivot for comparison, known as the Randomized Quick Sort algorithm. Simply add the following line before the code to randomly select an element in the array and swap it with the pivot element.

swap(arr, l, (int)(Math.random()*(r-l+1))+l);

IV. Java Example Code

Source Code Download: Download

QuickSort.java File Code:

package tutorialpro;

/**
 * Randomized Quick Sort
 */
public class QuickSort {

    // Perform partition operation on arr[l...r]
    // Return p, such that arr[l...p-1] < arr[p] and arr[p+1...r] > arr[p]
    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...j] < v; arr[j+1...i) > v
        int j = l;
        for (int i = l + 1; i <= r; i++)
            if (arr[i].compareTo(v) < 0) {
                j++;
                swap(arr, j, i);
            }
        swap(arr, l, j);
        return j;
    }

    // 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;
    }

    // Main method to test the QuickSort algorithm
    public static void main(String[] args) {
        int N = 10000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("tutorialpro.QuickSort", arr);
    }
}

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) {

    // Quick Sort is also an O(nlogn) complexity algorithm
    // It can easily handle data on the order of 1 million within 1 second
    int N = 1000000;
    Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
    sort(arr);
    SortTestHelper.printArray(arr);

}
}